The biggest difficulty you will have in building this system is not a technical one, but more political, and legal. You are going to be targeted by every government in the world. Government's will be your biggest threat, and I cannot see where you could possibly get proper hosting without some form of “backdoor/channel” for government agencies.
For example, here in the United States, you’d likely receive a National Security Letter which means you won’t even be able to acknowledge being forced to hand over keys. The government will likely tout terrorism, and crime as the reasoning for the NSL so you will spend a lot of time trying to get it off the ground in any country anywhere in the world. So onto the technical portions of this, along with the hurdles you will need to overcome to make it truly secure.
I will begin by answering your last question: “Is there something we are missing here?” Here is essentially what you are looking to do
PersonUsingService —> connects to your systems —> encrypt/decrypt email
Scenario 1) PersonUsingService’s machine is out of control. Any malicious software (rootkits, keystroke loggers, etc) means your system failed, even though it did its job. Imagine you built something got the attention of say EFF/ACLU, they used the service only to discover, their communications ended up on Pastebin. All they’ll know is it went through your systems, and in the end, your reputation suffers.
Scenario 2) PersonUsingService’s is MITM before reaching your server. In fact, governments place Narus taps at IXP’s, and or outright steal your certificate, or pay heavily to a CA. Your system fails.
Scenario 3) You take the time to create a wonderful schema but never secured your internal infrastructure, someone accidentally clicks a link while on your dev team. Allows governments, or rogues to access your key system.
I can give dozens of examples of why this is a losing battle. While I understand where you would come from in asking for such a system, the reality is, it is very complex not from the technological side, but from the legal scope.
Back to your questions: “Is storage of the (encrypted) private keys” (stopped here) NO ONE but the key owner should have access to their private key otherwise the system fails. The entire purpose of encryption were to keep private keys private. In an ideal world, there would be trust however, in what you initially stated: “People living in countries with totalitarian, oppressive and other threatening regimes” you need to remember these types of regimes have no problems using “Rubber Hose crypto" to access to your systems (and keys).
From the technical perspective, it is perhaps best to have a look at Vanish and the model put forth from them, and build around that. For example:
PersonUsingService —> log in —> create disappearing (24-48hr key) —> encrypt message
System —> 24-48 expiry —> erase keys
In something like this model, you needed worry about storing keys as the likelihood of a “rapid response raid” to get a hold of crypto keys is low. My perception of why no one isn’t spending time answering this, is because companies have tried this in the past (Hushmail) and burned through a lot of money doing so. Not to mention in the end, law trumps personal opinions, beliefs, etc. If a government declares you give up the keys, you have a lifelong fight trying to prove your point.