This is why it really needs to be done at the protocol level, an email provider can't change the behavior of my desktop client and the process could be completely automated for the average user.
Silent Circle and Lavabit seem to think it's better not to use email at all. An open Skype-like system is probably pretty good. Keys are ephemeral, and transferring encrypted files in audio-video sessions makes it hard to MITM.
The service would remain store-and-forward but the content would be encrypted throughout, something which is not currently possible without both parties knowing how to setup and use PGP.