I think the hard truth is that offering privacy at a premium will still detract total net revenue. Nobody really cares about a single person's search history. It's the conclusions you can extract from hundreds of millions of peoples' histories that makes data collection so powerful. The more people you allow to opt out from that collection, the less powerful your ad network becomes and the less big money spenders you will catch as a result. One big money spender can easily spend as much as ten thousand individuals with a single campaign. It's just not likely that there will be enough people willing to pay compared to giving them the services for free in exchange for their data.
