And what's a real shame is that they could still make money off of private users. It's possible to offer targeted ads based on unencrypted metadata and hashed keywords (c.f. some of the interested work GNUnet has done on search); they could also offer 100% private (client-side encrypted) accounts for an upcharge. Google's revenue per user is reputed to be roughly $10 per annum; I'd be willing to pay $50/year for client-side encrypted everything.
Yes, it'd cost money to maintain that infrastructure, but I bet there are enough people who'd want to do it, and would be willing to pay enough to do it, that it'd be profitable.
The revenue-per-user number (supposedly) reflects the revenue they're getting from that data. If they're making $X/user from data+payments, and Z users propose paying $XY, where $XYZ is more than sufficient to pay for the infrastructure and yield a tidy profit, why not do it?
Yes, it'd cost money to maintain that infrastructure, but I bet there are enough people who'd want to do it, and would be willing to pay enough to do it, that it'd be profitable.