I have the exact same issue. Being a professional DJ, I have to keep my music well organised, well tagged and I also make sure each track has its own album art embedded in it.
I use Media Monkey to tag.
Now, on my Galaxy S, no matter what player I use, some tracks show album art of another track and its just 2 or 3 pictures that show repeatedly on these tracks that are messed up. Its about 30% of the music that shows messed up embedded album art. Some tracks do not show a picture at all despite being tagged with album art. When I mount my SD on the PC and launch Media Monkey, all album art shows up nice and correct. Also, in Windows thumbnail view, all the art shows up correctly too.
I tried clearing Media storage data under applications but no luck. This is so utterly annoying!
What the hell is it with Android and embedded album art?