I've heard the same from a research librarian and a college professor -- both unsolicited opinions that came in the past week.
what where they searching for? IMO google gives pretty nice results for non-commercial terms.
I get much better search results in Google than in Yahoo or MSN. As for the question of whether Google search is deteriorating, I'd have to say "no." Example: It wasn't that long ago that a search for a digital camera would return page after page of affiliate spam or boilerplate dealer copy. Now it's likely to return results for the manufacturer's information page and high-quality review sites
how about the tripadvisor and yahoo travel 'be the first to rate city hotels' pages ranking everywhere in your niche, EFV? i personally hate that. it looks like it is enough to saturate your pages with the word 'review', auto-create zillion of pages and you get high position in google for anything you want within 2-4 years.