At this point I would format the card, make sure the Sansa is in USB Mode MSC and reload the card with folders that have been run through mp3tag with ID3v2.3 ISO-8859-1 as default (see my post above). A few nested folders shouldn’t matter unless the resulting path is extremely long–I think it’s 256 characters. E:\Music\Rock\Deafheaven would be fine.
Or if you want to keep searching:
Mp3tag will display what format the existing tags are in. You can just hit CTRL-A to highlight all the files in the album folder, Save Tags (with your default set) and have them fixed. Takes maybe 3 seconds per album.
You can also dump embedded art in the versions you have on the microSD card. In mp3tag, if album art pops up on the lower left when you are viewing a file, that’s embedded art.
View Extended tags, right-click on a file. You can save the image as folder.jpg in the same folder by clicking the floppy disc icon on the right. That is all the Sansa needs for art; it will display folder.jpg or cover.jpg for every song in the folder.
Then you can remove the embedded art from the files by clicking on the X. If all the songs on the album have the same embedded art, you can do the whole operation in bulk–highlight them all, save a copy of the art, use X to delete.
But you do have to be able to see the files. Try both USB modes again with the Sansa. Or, can you put the microSD into a card reader or some other device and have the computer read the files?