I am encountering a similar issue.
My images were in c:\MCCovers and I just added an MC directory to this name, modifying it to c:\MC\MCCovers.
I modified the cover art location accordingly.
I was left with quite a number of songs still pointing to the original folder, even after I deleted it. I also have a number of data and video files that point to the original location.
Selecting a file and saying "Quick Find in File" does nothing. The only thing that works is selecting each file, one at a time, and selecting "Add from File". Then I get the pop-up asking if I want to move the file to my cover art location--um, that's where I just browsed to get it in the first place!
So I'm not sure what is going on. It does not just happen with image files that no longer match the name of the file--it happens with image files that have the exact same name as the name field of the file as well (in the case of Data at least).
A search/replace sure would come in handy here. Without it, I've got lots of manual work ahead of me.'
Edit: in fact, I just checked, and I have over 900 files that are still pointing to the old directory. I honesly can't make those changes one at a time. And that's just for data & video files. Any advice?