It turns out Walmart has 500x500 JPEGs of cover art - only US-released albums, of course, but it might come in handy.
I figured that one out while paying a new visit to pugde's Journal, which has the following AppleScript nugget:
tell application "iTunes" set currart to artist of current track set curralb to album of current track end tell tell application "Finder" open location "http://www.walmart.com/catalog/search-ng.gsp?search_constraint=4104&search_query=" & currart & " " & curralb end tell
This can be placed in ~/Library/iTunes/Scripts for convenience (changing the URL for your favorite music site shouldn't be too difficult). There are no batch-oriented ways to re-tag entire albums yet, though.