Avoid collecting such information in the first place, which of course would require a different business model, which brings us back to the initial point.
Well, except that many users want full indexing of e-mails, including attachments, such that they can use an AJAX web interface to quickly search them.
So, storing all e-mails encrypted is not really feasible if you want to have such features as well [1]. It's a trade-off - convenience or security (I am sure someone will site Benjamin Franklin now ;)).
[1] Yes, I know that there is work on indexing encrypted data.
There is still a difference between storing the emails unencrypted and using them to profile users for ad targeting.
But anyway, what you are talking about could still be optional: if you wanted to search and be somewhat private you'd have to download the emails with a local client via IMAP - and if you really need search via web interface, you would toggle the option to store the emails unencrypted for that purpose.
Also, if you have a paid Google Apps account, you can disable ads in Google apps.
Personally, I'd like to see targeted ads more than 'random' ads. Of course, I don't like to be profiled. So, I use Ghostery, an ad blocker, and paid e-mail.
So, storing all e-mails encrypted is not really feasible if you want to have such features as well [1]. It's a trade-off - convenience or security (I am sure someone will site Benjamin Franklin now ;)).
[1] Yes, I know that there is work on indexing encrypted data.