Official comment
The auto-relocate is working, what's broken is that you imported the song, moved the file, the imported it again. When trying to relocate (either manually or auto), you tried pointing it to the same song that was already imported the second time ... and because you can't have two entries in the library pointing to the same file, you get that error.
Sort by song name for that missing file, identify its duplicate, look at the location or import date, and figure out how / why you wound up with that song being reimported vs. the original file location. Delete one of them, re-associate if necessary, profit.