This has been a little annoyance for me too. I was prepared to accept no art for Ogg even though it's my format of choice, since my understanding was that there was no officially accepted way to embed images in Ogg metadata (although various developers have settled on various more or less usable approaches). But I've got plenty of MP3s that should have valid images embedded, and I've never seen Android pick up any of them. Fortunately, your post motivated me to do a little searching and see if I could answer both your questions, and I think I can.
Second question first: "Does anyone understand the format and naming system used on 'albumthumbs'?" Yes, but you're not going to like the answer. I tracked down the source code for Android's "MusicUtils" class, which you can read yourself in their version control system if you wish. Apparently, when the system finds art embedded in a media file that it does not already have cached, it copies it out to the albumthumbs folder with a filename generated from a call to Java's System.currentTimeMillis() method. (You can see this around line 909.) It then stores a reference to this file along with an "album_id" that was generated when the library first recognized the album in the internal database.
So the filenames are completely arbitrary and depend on when the system first found art for an album. Only the internal database knows which file goes to which album. A nice efficient process for the software, but fairly opaque and un-hackable for the user. It does, however, explain why your trick works: Since the MP3 and Ogg versions of the files have the same metadata, the library will recognize them as belonging to the same album that it already cached artwork for.
Now, the other question: "Is there a better way to solve this problem?" Well, maybe. Depends on how you structure your audio files on your SD card. Further down in the "getArtworkFromFile" method (starts around 997), I spotted a little secret. If the system fails to find cached art, and it fails to find embedded art, it will look in one more place: A file in the same folder as the audio file named "AlbumArt.jpg".
Now, for me, this is not completely good news. I do have album art as separate files for almost all of my albums, but it's named "Folder.jpg" to take advantage of Windows' folder thumbnail feature. (I use foobar2000 as my PC player, and it apparently will recognize either name.) Also, it's been my habit to date to dump audio into Android's "Music" folder with no subfolders, although I do keep them scrupulously organized on the PC. I usually delete a song after one or two listens and constantly refresh the pool so it didn't seem worthwhile to structure them. It's going to take a little work for me to figure out how to make foobar2000 put fairly random selections onto the SD card and retain the folder structure and include the artwork file and (if possible) rename the file to "AlbumArt.jpg" for me. If anyone's got any tips on that, speak up.
Nevertheless, I did a test and verified that this will work. I put one of my album art files into the Music folder and named it "AlbumArt.jpg", and this artwork then showed up on every song I played.
