Just to clarify, iTtunes stores the artwork in up to 3 formats (128x128, 256x256, 300x300 or 400x400) in separate ict2 files.
These itc2 files are stored in Sub Directories under: My Documents\My Music\iTunes\Album Artwork\Cache.
The name of the itc2 files consists of the Library Persistent ID and as second part the Persistent ID key for your music file in the iTunes library. example:
(note: The Library Persistent ID should always be the same)
The Library Persistent ID and the Persisent ID for your music file you can find both in the iTunes Library.XML file
<key>Library Persistent ID</key><string>AFDECED0FACD54DC</string>
To extract the itc2 to image files, use http://mark0.net/soft-bitmaprip-e.html
, it's a lot of work, (So not the quick fix you're looking for) but you can recover most of the artwork.
If you tag your music files with Images larger then 400x400 you will have
to re-download / search them again as the max. size that iTunes stores is 400x400.