All of this has been discussed recently. Search a bit around, but the short version of the answer would be:

a) There is a program (the name of which I don't recall) that is able to 'normalize' MP3 tracks without de-compressing them; moreover, it can do that on tune-by-tune or album-by-album basis. However, as Tony, Doug and others often stress out, perceived difference in volume is usually there owing to different amount of volume compression, not incorrect normalisation.

b) MusicMatch will do CDDB lookups based on partial tag data. MoodLogic will 'recognise' about half of tag-less tunes (depending on how mainstream they are, I guess )