I believe mp3tag (all in lower case, and is free, not to be confused with MP3Tag, which has capitals and is not free) has some pretty powerfull scripting functions that might let you built tag portions of your music based on file names.
You will need to do some manual interventions, but you can get the builk of it done for you. For example, you might need to seperate all the tracks names <artist> - <track>.mp3 and run a batch on them, then do the same for <artist> - <album> - <track_no> - <track>.mp3, etc.
Once you have things a bit more consistant, some of the other apps should then be able to go out and complete the missing data for those tracks.