Yes it is. Or someone would have done it by now.
> When receiving mail, store the sender's public key
You mean "the public key associated with the inbound email". You don't know anything at this point about how it relates to the person you're intending to correspond with, because the key could be MITMd.
Also, this approach does nothing to solve the fact that most people would prefer webmail and mail synced across multiple devices, which is an even more painful key management problem.
That's true, and my paper mail envelope could be steamed open, read, and resealed as well. I'm not saying this would result in perfect security, and anyone would be foolish to treat it as good enough to direct their U-boat fleet. But it would be pretty good for routine email.
As for the key exchange, if a user is worried about it, they could exchange keys in another way. The point about the built-in key exchange is that it happens by default.
> more painful key management problem.
It's only painful if you really need high security. I'd just like something better than postcard security.
Then, when sending mail, if there's a public key for the recipient, then encrypt it. No user interaction is required.