I have some speculation on this. Are you sure that your frustration comes from unusually poor results? Could it be that we're so used to things being perfect now, that a page of mediocre results looks like the end of the world?
Look at 2000. No Shazam. If you heard a song on the radio, that was the end of the story. There were some services you could call for $5 and a human would help you identify it. Now in 2011 you press a button and wait 5 seconds.
The web had a lot less information on it. A few hundred million people were connected. Now, in 2011, a few billion people can connect. Huge shift in quantity. Very tough to keep the S/N going strong.
2000: No Wikipedia. Now in 2011 if Wikipedia isn't in your top results you might be upset, but in 2000 you were happy even though Wikipedia didn't yet exist!
So I pose the question to you: Are you absolutely, positively sure that Google's quality has declined and what you are seeing isn't just a side-effect of everything else being so awesome?
I think there's also a problem that the quality of content that Google has to index is steadily declining. In the 90's, many people were keeping lists of links to good stuff they found on the internet. Google could crawl the links and make conclusions. Now, people hardly do that anymore because they can just google it.
So Google has to employ ever more powerful algorithms to maintain even the same level of search quality. I think here lies an existential threat to the search engines.
That doesn't detract from the fact that results are bad for many searches and that the google monoculture has thwarted it earlier success. I'm absolutely sure that my satisfaction with their product has declined. I know I look forward to a better search engine than google. In 2000 google was the better search engine.
Of course you were impressed and satisfied with Google back then — it was so much better than the alternatives. I'm sure you would have been just as (perhaps more) satisfied if 2011 Google existed in 2000. We've had 11 years to pinpoint the deficiencies of Google. Couple that with 11 years of rapid progress on the internet — we just expect more now.
What's confounding to me is that there's an obvious solution to Google's biggest problem (spammers and scammers):
1. Allow users to individually block URLs and domains on a permanent basis.
2. Accumulate massive amounts of data regarding blocked URLs/domains (a good quality indicator)
3. Integrate this data into the PageRank algorithm
I'm not sure why it's taking Google so long to do this, at least step 1.I do a lot of Perl. It used to be that as soon as something on CPAN matched my search, I'd get a handful of results, then it would find the CPAN match, then I'd get pages and pages of the same result from different CPAN mirrors. Now that no longer happens, and my searches for half-remembered Perl discussions are much, much less likely to end in frustration.
But that's me, and YMMV.
I didn't keep a record of my searches from 2000, but I do remember that I was extremely impressed and satisfied with google back then. That is no longer the case. I am frustrated on daily basis by the results of many searches.
It's not really your fault though. I blame it on mono culture. Google has such a huge hold of the search market that it's probably not even worth SEO peoples time to bother gaming other search engines. There is a whole industry feeding off your success and we all suffer for it.
After the china attacks earlier this/last year google put out a decree that they would phase out windows machines among their employees. I thought it made sense. Windows is too easy a target because of it's success. The same is true in nature and the same is true in search engines.
The best we can hope for is a new search engine that will be insignificant enough in terms of market share to avoid the scammers. As long as google is the dominant search engine it will never get better.