Are you sure that the art is actually imbedded into the ID3 tag? Some applications don't actually write to the tag to show the album art. i.e. iTunes is pretty flakey with album art. Works well for itself, but if you use it out of the app then it gets weird.
Anyways you can use Media Monkey to embed the album art to the ID3 if it really bothers you.
You can check out this site on a how to.
If you have questions just post back.