sentinel's answer is now 7 years old but still works... almost. It won't work currently as stated.
Modifying it slightly, here's the new procedure as of 4/4/2017:
Create a new playlist called "Exists". Do not select any music first, just create it blank. If you select all and "New Playlist from Selection", iTunes will NOT verify the songs, so don't do that. Just create the blank playlist.
Select-All on your music and drag all the songs to that playlist. This will take a couple minutes to process, as it's verifying that each song can be found.
Optional - Select All on your songs again and try to create a "New Playlist from Selection", to an "Exists - Old Method" playlist. Then compare the song count of that playlist to the song count of the new method's "Exists" playlist. The new method will have fewer songs if any weren't found.
Same as the old method, create a Smart Playlist named "Not Exists" or whatever, with rules "Playlist is not 'Exists'" and "Media Kind is Music". Right click and update if it doesn't update on creation.
That playlist will contain all the songs that weren't found. If you know they were just duplicates or whatever, you can simply select all, right click, and "Delete From Library" to clear them out and leave the non-duplicates.
That cleaned up my own library after I'd moved some directories around and re-added them.
And until I did that, Sync'ing to my iPhone was erroring out on some of those duplicate songs and thus not syncing the songs at all, even the duplicates that DID exist.
Thanks for pointing the way, sentinel!