I agree that Genre and Date are two of the hardest tags to get right. A distant third is Cover Art, although I have been surprised recently at some of the more obscure albums that MC has found cover art for.
Regarding Date, I have found that MC's "Playing Now" feature is a great way to fill in an album's release date. In case you haven't tried it, clicking on "Playing Now" takes you to an Internet music database that has biographies and discographies of many bands. It's also a handy way of getting cover art without the hassle of scanning (you can cut-and-paste from their web site to MC). Another way to fill the date is to do a web search for "<song name> <artist name> discography".
Regarding Genre--I find Genre to be too limiting in most cases. I divide my library into two categories: "Genre Music" and "Regular Music". Genre Music is music that is primarily defined by its genre and which I usually listen to at certain occasions, but not when I'm in the mood to just "listen to music"--e.g. Ambient/Background Sounds; Capoeira songs; Electronic Beat/Trance; Funk; Electric Guitar Rock (e.g. Joe Satriani). "Regular Music" is nearly everything else. Stuff that I listen to when I'm just listening to songs. I used to try to sub-divide my music into genres like "Alternative", "Punk", "Pop", etc... but I found that these genres weren't descriptive enough, and when I tried to get really descriptive, then it was so much work that it wasn't worth it. Like, for example, is Third Eye Blind, "Punk"? The ever-generic, "Rock"? "Alternative"? Who knows? What about Green Day? They're typically considered Punk, but should they really be in the same genre as the Sex Pistols? Argh.
Now, what I do is I use the Custom 1 field for my genre-like smartlists. I have smartlists like "Dark", "Happy", "Soft", "Pop Singles", etc... The rules for these smartlists are:
[custom 1]="dark"
[custom 1]="happy"
Etc...
Then I put the relevant keyword in Custom 1 for each track. The nice thing about this method is that it lets me put each track in multiple categories--e.g. by putting "dark soft" in Custom 1, the track will match both of those smartlists.
I also use this to create decade-based lists (e.g. "2000's", "1990's", etc...). I create a list of songs by decade, but I can be selective and not play every song in my library from that decade, as I would with a Year-based smartlist. For these playlists, I try to focus on songs that would have been on the radio in that decade.