[asdafa]

Try this: http://www.autistici.org/en/get_service.html

However forget about the second optional requirement. The way the SMTP works, means that at some point your email messages must be read and processed by the server, if you can't trust it, you already lost. The only way to be "safe" in that regard is to encrypt the payload with GPG as already suggested.

Furthermore, server-side encryption of your stored emails is indeed possible, but it will render impossible for the provider to offer basic functionalities like search in the web ui.

If you're really concerned about privacy issues and really want all your email encrypted you might be better off self hosting your own mail server, but be warned if you don't know what you're doing and you don't take proper care of it, you'll end up in a situation that is even worse than using something like gmail.