The searching is part of the problem, it's just too much effort. Build checking whether a public key is available via the STMP servers, do it transparently wit

The searching is part of the problem, it's just too much effort. 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.