Official comment
1) Sort by name. You'll probably notice that the duplicates are the ones added recently, and the missing tracks are the old ones... but those ones have your cue points, etc.
2) Sort by date, this should allow you to add a MyTag to the duplicates (heck, tag them as "Duplicates") and then sort your collection again by other methods to verify the "Duplicate" tagged files are the ones you want to remove from the collection.
3) Remove the duplicates by filtering down to that "Duplicates" tag
4) Run the relocation process... several dozen times. It's going to be a pain because you allowed iTunes to manage the locations of those files, but it should eventually link all of the files back to their entries in the database.