I believe the answer what you suggested, that is, do a search and replace on the filename field to point them to the new location, BUT I believe that if you do this when the database is "live" MC will attemp to move the existing tracks to the new filename (which will end up renaming them all with a (1) on the end).
So, what you need to do is:
1. Disable autoimport and shutdown MC
2. From Windows, rename the top level folder under which all your tracks exist to some temp name
3. Restart MC; it will not be able to find and tracks now
4. Do the search and rename in the filename (or Filename (path)) field
I would definitely try this with a small subset of your tracks before doing them all.
Good luck.