Imo the problem mainly lies in Google's square. All SEO tools exist for the reason of it being possible to game search results in the first place. It's inevitable that companies will offer tools and services to do so when there's such a huge market for it.
Google has gotten better at discerning between crap and quality content, but they still have a long way to go, and I'm unsure if it can be fully fixed the way search engines currently work.
Personally, I've given up hope Google will be the one to do this. They have serious talent and no one can deny this but IMHO Google lacks vision and leadership. They've simply lost their way.
Even their search results have gotten worse and worse.
Google's fix for spammy results seems to be favoring large corporations, governments, and putting results on their own page (so-called "rich results" fka "rich snippets).
Google has gotten better at discerning between crap and quality content, but they still have a long way to go, and I'm unsure if it can be fully fixed the way search engines currently work.