iTunes library pointing to completely wrong files
I would suggest a combination of your first and last ideas. You could re-add your Music folder to your library, and then use a script to change the location of the old entries (correct metadata) to the new entries (correct locations).

Pseudocode rough draft:

for every song in the XML file (seek)
  search the rest of the XML file for other songs of the same name
  if only one is found (found)
    log seek's name to file1
    if found is newer than seek
      copy found's Location value to seek
      remove found
    else
      copy seek's Location value to found
      remove seek
  else if more than one is found
    log seek's name to file2 (for manual editing)
  else (no others are found)
    log seek's name to file3


This script design would assuredly be quite inefficient, but it would fix most problems itself, and you would (er, should) only have to review the songs with more than 2 duplicate versions.

See this answer for details on how to make these XML changes take effect on your library.