The use of PROJECTNAME neatly solves this issue. Previously I hated using it, but I've come to REALLY appreciate it.
I wrote a tool which would open up any number of drawings IN MEMORY, and change the PROJECTNAME setting, as well as strip any hard paths from XREFS.
This runs over several hundred drawings in literally a few minutes.
Unfortunately I can't give this out, however I do have a suggestion. Create a script that adds a certain PROJECTNAME into AutoCAD and add the paths to it. You could do this at AutoCAD startup with a bit of lisp/vba as well (vba is how I do it which reads from a master .xml file).
Then run a script over every drawing which changes the drawing's PROJECTNAME to the newly added one. Since the new PROJECTNAME has your NEW paths in it, your REFERENCE files should be found.
I hope this helps.
Cheers,
Glenn.