I remember, back in 1997, how magically good Google's search results were compared to other search engines. I'd look for something on Hotbot and somewhere in a sea of seemingly randomly ordered keyword matches might be the relevant result. But Google! It was often the first thing. We passed the link to the new search engine around, just to show each other how magical it was.
Times sure have changed. I don't expect that behavior now. Google is still the first thing I try, but I'm often much better off following an approximation of their original algorithm by hand - searching relevant communities of interest, looking for prominent links.
Maybe SEO won. Maybe the web changed. Maybe Google changed. Maybe all of the above. We're all poorer for it.