The solution for Google...
...is to become a search engine again.
I haven't taken google searches seriously for aaaaaaaaaaages because of all the crap you get launched at you that has nothing to do with what you searched for.
In spending so much time trying to combat black hat SEO and the like, they've algorithmed themselves into a corner. Their ranking system has probably become so bloated and biased that it's not really a ranking algorithm anymore, it's just a complicated black list to fight off bots, link pyramids and keyword stuffing.
Biting the hand that feeds IT
