I've detailed this problem before but was accused of being a whiner. "this is a phone not an mp3 player, go back to your iphone,blah,blah."
It is interesting to see others have the same problem.
This is what I know:
The media database gets corrupted. I looked at the catlogs thru a debugger and can see where the music player trips or fails to find the correct album art. If you plug your phone into the SDK and launch ANY music app (Doubletwist, MixZing, stock HTC,whatever) you will see how it works in realtime in the debugger window.
Renaming your folder Music to MP3 is only a temporary solution. Best bet is to reformat your card everytime you synch your music over or make a habit of making "UNIQUE" folder names so the media players re-scans and re-analyzes the music files. It will re-scan and pick up the album art. Everytime it re-scans, it stores the file information into a SQL3lite database. This is where it gets the album art in the player.
It simply re-reads from the database. I assume they do this for performance and speed reason. It will be too slow to always read the ID3 tags. It doesn't read it from the file after it gets scan. So if you continue to add new music to your existing Music folder, it will get corrupted.
I've made a habit of naming my music folders by date like this:
MUSIC_07232010
Then on the next day I re-synch, I reformat and make a new folder
MUSIC_07242010
I basically force the phone to re-scan my music and store the new info into the media database.
I have to say.. This is one thing Apple does 100% right. I've never ever had this sot of ridiculous mismanagement music problems.
All my music is purchased 100% from Amazon music store, standard mp3s with correct tags, and all the album art are embedded. I don't need an Android app to re-download album art. What I need is HTC to fix this problem.