It seems like it could be done with a service offering public key info, and using key signing and web-of-trust to keep the keys reliable, and encrypting in open source client software not provided or updated by the mail service provider.

That still leaves the service open to being strong-armed into sending you malware. And, of course, your mail headers are in the clear.

But, apparently, to the Lavabit people, what I've outlined here isn't sufficient, and the implication is that the NSA and/or FBI has ways of compromising all email providers no matter how they operate.