I agree. Its a pretty tough problem, however it is good to cross the bridge when it comes. If the search engine stays really niche, perhaps it may not even be worth it for the spammers, while doing enough to cater to the somewhat self-selecting audience. For example, the number of people who want to get to the front page of HN is likely to be a really minuscule fraction of people wanting to get to the top of search results.
Also, I wonder if is it possible to detect promotional content by analyzing things like call to actions and such?