Lately, I've found myself feeling like search is back in 1999 again.
When I joined Google in 2000, one thing I did was run a bunch of searches and save the results. When I went back and looked at the data, Google2000 can't compare to Google2010. Google2000 still had lots of spam--it was much, much better than Altavista or other competitors at the time, but the results weren't nearly as good as they are now. I keep meaning to do a blog post and show some examples.
One example category does come to mind, which is a frequent pet peeve: lyrics searches. They definitely return sort of crappy results currently, but I can't say for sure what they returned in 2000, since I didn't save any results.
Examples:
Imo [joy division walked in line lyrics] should return a page like http://www.joydiv.org/shadowplay/joyd/walkedline.html. Instead it returns a bunch of sites like lyricsfreak.com, sing365.com, lyricsdepot.com, metrolyrics.com, etc.
The case is even stronger if there's actually an official site for the musician with official lyrics. An example of that: [vnv nation fragments lyrics] should return http://www.vnvnation.com/Webfiles/lyrics/fragments.htm, but instead it again returns the usual lyrics-site suspects.
I think my recollection is that I used to get fan sites more than lyrics aggregators in 2000. That might be more due to web changes than Google changes, admittedly, since many of these lyrics aggregators didn't exist in 2000, and hobbyist fan sites may have been more vibrant. The fact that the same lyrics-aggregator sites dominate for almost all the searches seems weird, though; it seems that basically all lyrics searches return "big lyrics site", rather than trying to retrieve a site specializing in the band I searched for.
You're spoiled then.
But it doesn't actually move the conversation forward at all.
Spoiled? I remember search being horrendous back in those days. It was almost exact word matching and it took hours to find relevant results. Google was a breath of fresh air back then (especially since they didn't run all those X10 ads and popups ala Yahoo!).
I've switched to Bing a few months ago for tin-foil-haty reasons, and also being disappointed in the way Google interpreted some of my queries (for some reason the plus sign doesn't mean anything anymore).
I occasionally use Google when I give up on finding something on Bing, but 99% of the time 4-5 results of the first page are pages I already found on Bing, with the rest being irrelevant results.
I too wasn't aware of the search tools that Matt Cutts mentioned above, I'll give it a try the next time I'm having a hard time finding something with a date restriction.