A number of features I expect from e-mail seem rather between hard up to impossible to achieve if you insist on the "your server cannot be trusted, either" model of operations, though:

- The ability to login from multiple devices (using both dedicated clients and webmail) and subsequently being able to immediately access all my old messages, too.

- Global filtering, tagging, folders, read/unread tracking etc.

- Full-text search that doesn't require downloading all messages to your local device beforehand.