We had thousands of dead/broken tracks (had the little exclamation point next to them). Fixed it with this method. Took about 15 minutes. http://paulmayne.org/blog/2007/11/ho...s-from-itunes/
Sounds like your problem may be a little different though, so that may not help. There are some paid programs out there that will clean up your library and do so by examining actual song content and not be fooled by names, etc. I'm not aware of a free solution.
Once we got our library cleaned up we took the opposite approach from you and turned ON 'keep itunes media folder organised' and 'Copy files to iTunes media folder when adding to library'. This takes up a little more HD space, but puts everything in one place where it is consistently labeled and easy to manage. Most of our previous problems had come from having tracks spread out everywhere, inconsistently labeled, and accidentally reimporting or indexing them. It also makes it easy possible to move the library later, including the actual music content. We now have a library of almost 250GB, but it has no duplicates, and everything is labeled the same way.
I use iTunes, but I hate it. When it isn't crashing it's making a mess of things.