What about Dogpile? (http://dogpile.com)

I guess that solves half of the problem - allowing you to compare results between engines should keep them "honest".

But the barrier to entry for a new engine would remain as high, or?

So, do we get around the server costs by daisy chaining? Your search front end queries a few search providers, which mix their own content with the cached results from a few others, and so on.

(This is my own, in case that wasn't already very clear... I hope for forgiveness on the basis that it's not totally rubbish)