I don't think you or I, or even Google knows the total set of their options, but we can sit here and come up with some alternatives.
>Only at the cost of not providing the service that users want, which includes such things as fast, full-text email search,
e2e encryption is completely compatible with fast, full-text email search. There are several companies that currently offer such services, that is webbased, fast searchable email, that is e2e encrypted such that no plaintext arrives on the server side (unfortunately I am under an NDA or I would tell you more but you can read the papers if you like). Stuff like this: http://www.forbes.com/sites/andygreenberg/2011/12/19/an-mit-...
It's not just databases it's search engines as well.
I think gmail probably loses some enterprise clients because they don't do this, but I expect "enterprise level" features like this from gmail in ~2-3 years by my guess. Probably sooner due to the nosedive in trust they just took.
Google has a monopoly on new email account creation so they don't need to innovate to get new customers (hell android locks everyone in). It isn't outlandish to suggest that they could have chosen to innovate and done what has been in the research literature for some time now. Secure e2e encrypted cloud email.
>recovering accounts after passwords (and other security tokens, if any) have been lost.
Have you tried to get gmail accounts back because I know people that have lost all their email. Are they better at this now (maybe they are, I hope so)? Even with this as a requirement, it is achievable. The user's client just sends a copy of the key to a foreign key escrow service that will unlock their account if anything happens once they prove they are who they say they are with various forms of ID and proofs of knowledge. Paranoid users can elect not to do this. Or ask people in your circles that you have marked as trusted to attest to your identity. You could do some clever threshold cryptography with your closest family and friends.
They big trick is making money off ads while not learning about the contents of the email. One way could be a bounded leakage strategy whereby the encryption scheme allows some ad matches without giving up more than one or two popular words per email.
All of this is a sideshow though. The NSA wasn't going to throw the Google execs in jail for not towing the line. Google is an extremely powerful company with a strong lobby in Washington. Not to mention that just pressing the charges would be a major embarrassment for the NSA. Twitter fought and won. Likely they just offered Google some nice contracts with the US government.