How about adding some sort of a feedback mechanism to search? For instance, when I search for something, maybe some way to mark a result as spam and optionally relevant?

The obvious problem is that spammers would attempt to game the feedback mechanism. But a combination of things like captcha to defend against robots, limits on how many times you can flag/upvote sites in a month (feedback credits), and exposing the feedback mechanism to only real, active-for-a-long-time users above a karma threshold (Google can definitely figure this out looking at the search history, gmail account etc), might be strong enough to beat the spammers.

You could start this as a Labs feature, and see if it works well.