Official comment
Simon,
If rekordbox tells you the songs are already in the collection when you're trying to relocate, that means they were imported twice; once from the old location, then they were moved, and imported again.
The solution here is to find when they were imported a second time, sort by date, remove the duplicates, then relocate.