Google ads provide enough value for me on some searches that I would actively seek them out.
I think I am extravagating to say I would actually pay for the ads, but I'd choose them over a free service without ads.
Selling an ad-free version of their services would undermine the value of the audience presented to their advertisers.
It would also be tantamount to admitting that their ads are annoying, if even in a minor way, and this would contradict their efforts to deliver relevant ads unobtrusively.
Google, by it's past record, is a company I can trust (ofcourse only to a certain extent) with my data.
Facebook on the other hand...
EDIT:
Related: Would Twitter be better if your paid for it? : http://gigaom.com/2012/07/22/free-vs-paid-would-twitter-be-b...
[1] http://blogs.smartmoney.com/advice/2012/01/25/who-would-pay-...
The more hypothetical, but interesting question: if you had to pay for it to use it, how much would you spend? Assuming no free bing substitute, I'd gladly shell out $1000/year.
Or maybe $x per 1000 searches.... I dunno