Of course that implies these services to actually care about security for their users this much. There are a ton of things major companies could to do make end-to-end encryption mainstream and popular. The problem is they have no interest in doing it, and not enough people are asking them to do it.
But I'd like to think that in a Post-PRISM world where nothing changes at the government level, there would be more services popping up and offering these "features". It's what competition is supposed to do.
Build checking whether a public key is available via the STMP servers, do it transparently with designated trusted pub key repos much like browsers have trusted CAs or something along the lines of dns.
Problem still stands, lose your pub key, all mail signed with it is lost to you and people will complain. You could offer a service that allows folks to store and retrive the pub key, but that kinda misses the point because anyone who stores that info can hand it over to the NSA et all.
Other problem with this is the .GOV could MITM this service, give you a fake pub key, read the mail, then resign with read pub key and send it on. You need your mail client to actually register the pub key on first send and hope you weren't always being intercepted from the start, and give you a warning when the key changes.
Do you encrypt all your own e-mail, as a result of this stuff?
No, that’s really hard.