How does that solve anything? Either these services will have to publish the key on your behalf (so you can lookup the public key for bob@gmail.com with some public API), or you will have to provide the public key every time you hand out your email address.

The former doesn't fix the issue at all, and the latter is unworkable because the guy reliably giving out the wrong email address will absolutely not remember his public key.