Kagi.com which I mentioned upthread is exactly that: paid search engine with no ads. It’s free during beta.

I don’t mean to sound like I’m advertising it but I agree with you and I hope it can garner some interest.