iTunes library pointing to completely wrong files
Solution 1:
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.
Solution 2:
Try moving all the files back to a case-insensitve drive.
This stumped me forever until I figured out the problem. It wasn't until I started to manually correct the problem files that I noticed a common theme in the problem files. "of" vs "Of".
Last year I migrated all my music from a case insensitive drive to a case sensitive drive. Suddenly many of my songs would not play and point to completely different files on the drive, be it jpg images or whatever.
I had to write a script to compare the itunes xml to what was on the drive and figure out all the discrepancies. Regardless...it is a bit of a time consuming nightmare to fix.
If you delete files out of your iTunes library and re-add them, DO NOT click "move to trash" otherwise it will delete whatever non-music file iTunes is pointing at. (!)
Solution 3:
And for you humans out there that don't write code...
This happens with movies as well. Ex. I play Lord of the Rings, I get The Martian. Has gotten buggier and buggier since (not too soon) Tim Cook took over. So now we pay Apple prices for Windows performance. Thanks Obama...I digress.
Quick trick works for me. Using the example above, intentionally play the movie that unintentionally ruins date night. I.e.The Martian. Close it. Play the movie you want. I.e. LOTR...and you, Sam and Frodo are reunited. This works for me, and the other 95% of people that don't write scripts to listen to a song or play a movie.