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.
