Don't be too sure that the pictures are inside the files if youuse WMP as test program ... as WMP keeps a thumbnail library so it needs some forced updates to get rid of the ´pictures.
If you load the files into MP3tag, though, and apply the filter (press F3)
NOT %_covers% iS ""
and all the files remain displayed then the art is embedded.
To save your other MP3 player from the junkyard: you can export the embedded pictures with an action (see FAQs /t/967/1 so that only one file per folder is created. Also you can determine, which name should be used - for WMP this would be folder.jpg. Check, what your MP3 player expects.