Hi,
This is a problem I've seen in both WMP and iTunes. The real issue is with non-purchased music in your library. Lots of music that's copied from public sources such as uTorrent and Pirate Bay don't have good copying software (as this is done by people on their home computers), and they don't get all the attributes of MP4, AAC, MP3, etc. necessary to include the Album art. There are free programs out there that attempt to correct this, but none I've seen do 100%!! An example of this is FixTunes for iTunes, which does a pretty good job on pilfered or non-purchased music.
To fix this problem, delete ALL your music from your hard drive after backing up to external media first (if you haven't done so already). Then...