I found the rather good Album Cover Art Downloader which automagically downloads the images it thinks you want and lets you decide if they are correct. (n.b. you may have to switch to a proper OS to use this program – i.e. not Windoze).

It did the whole job in an afternoon. Unfortunately, my Video iPod or possibly gtkpod (the iTunes alternative for Linux) can’t seem to handle more than about a hundred pictures, so the whole point of them being there is defeated – at least until gtkPod is fixed.

BTW, I jest about it being not worth it. I’m just a little peeved about the bug in gtkPod :(