I have a large music collection, but early on I got into the habit of removing ID3 tags from the songs because they didn’t really fit into what I was doing at the time. In hindsight, I realize that this wasn’t the best idea. I’m just wondering, does each mp3 have some sort of unique characteristic that can be analyzed to re-create the ID3 tag? By this, I mean something that would analyze [whatever unique properties mp3s hopefully have], refer to CDDB, find the match, and then write your tag for you. Does this sort of program exist? Is it even possible? Does anyone feel like making it and sending it to me? 
Not currently. The CDDB works by reading a serial number off of the CD itself. Without a globally unique identifier like that, it’s impossible to automagically fill in the ID3 tag.
Now, I suppose someone could set up an alternative to the CDDB (let’s call it the MP3DB) that would hash your MP3 and pull the data associated with that unique has value out of a database. However, nothing like that exists, and I suspect that the RIAA would attempt to shoot it down if it did exist.
Even in principle, the mp3db wouldn’t work. If you encode, say, Yesterday with two different encoders, the resulting files may have nothing in common.
Did you at least rip your songs with a file name that includes all of the meta-data? For example, many people rip all of their music into an artist directory followed by a album directory. Then they name the file using the track number and song name. If you did something similar, then you can re-create the tag data this way.
I just finished writing an MP3/WMA tag editor that “cleans” your tags based on both the existing tags and the song’s path name. It takes all the info that it can find, looks it up against Gracenote’s music database, and then returns the best matches.
Actually this does exist - or at least is beginning to exist. Gracenote has a Music ID service that does exactly what you described. Check it out here. There are other organizations creating the same service. I think one of them is free and based on FreeDB (maybe called MusicBrainz).
Not sure that the RIAA would object. It really isn’t any different that looking up the CD’s TOC data and it doesn’t involve a copyright violation.
Also, to UltraFilter’s point, the hash algorithms sample the decoded MP3 at a lower rate so that differences in MP3 encoding are ignored. That is, the same song ripped at different bitrates will still match the same hash ID.
Check out MoodLogic, which identifies MP3 files, corrects the filenames and ID3 tags, and also categorizes them by a few subjective properties. I believe it simply generates a hash of the music data (sans ID3 tag), and it only works if someone else has already identified that file, so it might not work if you’ve created the MP3s yourself or re-encoded them.
CaveMike, my naming system goes as follows:
Genre – Artist - Song Title (feat. Various Artists)
I’m going to try out some of these various available methods and see if any of them can do what I’m looking for. Wish me luck!
I use a tagger program (sorry, I don’t have the name right now, but I can look it up when I get home) that allows me to write properties to multiple MP3 at once.
For example, I open a folder, shift-click all the Mp3s, and fill-in say, the ‘Artist’ field and click ‘OK’. It then applies that artist name to all those MP3s.
That’s the best I’ve found for doing multiples so far.