Bulk Update Cover Art

I have about 36,000+ mp3 files that are all tagged with cover art. Many of them are low quality and with New AppleTV and larger LCDs I need to update all the cover art to larger file sizes.
Can this be done easily in a batch mode with MP3TAG?

This depends an awful lot on whether you have the new pictures already in the file system or not.
And even then it may be tricky if you have not applied a consistent naming scheme.

If you still have to search for pictures somewhere in the Internet, you have to treat the files picture by picture (modify all those files at once that get the same picture) if you want to use MP3tag.

I would suggest that you have a look at the albumartdownloader (freeware tool).