MediaJukebox, from its 2001 version to its new, free version does a great job. Point it to a folder and run import.
If the MP3 files (the tags) are really messed up, it will not import the files to its library (this is also true of Windows Media Player; these are files that if you select them, they play fine, but they do not import to many, maybe all, players databases).
After the import there will be a playlist created called "recently imported". Ctrl+A, select the whole list, and then right click and select library tools/fill properties from file name. This assumes your filenames are consistent and have the track name, number, artist, etc. in them some place (folder structure or name). If they aren't consistent, you can select groups that are and do the fill properties from filename in pieces instead of one big bang.
It will rebuild library data data from file/folder data. Now do a library tools/update tags from library. Things will be much better and now Windows Media Player will also be able to find the files and put them in its library.
Unfortunately you will loose stuff like genre and maybe even the bitrate. However, from what I've read, most MP3 players ignore the tag data when they play the file, maybe the bitrate is just a memo put in the tag when the file was created and useless except for information.
You can now convert the files to
ape or whatever and get away from problems caused by random changes to the MP3 tag which makes it appear you have different versions of the same song.