Just because I REALLLLLY like talking to myself, here's what I did (if anyone is interested).
I've got MC12 set to save cover art in a folder, and also embed it in the tags (because nobody can make 2 different players which use the same standard). I selected my files, and told MC12 to "Remove Cover Art". It asked if I wanted to get rid of the art files as well. I told it most certainly NOT!
Now I had a big library with no cover art. I selected everything again, told it to "Quick Find in Folder/Cover Art Directory". It complained about it was going to take a long time. Yeah, I'd already figured that. It started working, and I went to sleep. When I left for work 11 hours later, it was still at it, with about 3300 tags left to update (out of just over 9000).
When I came home, MC12 was nowhere to be found. I restarted it, and it complained about crashing, and wanted to do all sorts of lame start-up stuff. I told it to just start normally. It took a bit, but all the cover art came up (most of it even correct). There were a few items I had to go back and re-do, but considering it was dealing with over 700 albums and it was mostly a hands-off procedure, I was quite satisfied with the results.
Now if I could just get the #$^&@ Kenwood DNX-7100 to play randomly off the USB input. I've got a cute lil' 60 GB 1.8" external USB drive just achin' to be used...