S/MIME actually solves the key problem pretty nicely, every signed mail contains the certificate that is required to send an encrypted reply.
Just start signing your mails.
Sure it does. The information in the certificate is signed (by the intermediate CA) and will contain a certificate chain that leads to a trusted CA and the email address and possibly even the subject's name will be encoded within the certificate. If you can trust the root CA, you can trust that the other party is who they say they are.
Then we get to argue whether NSA can get bogus valid certificates from the commercial CA's... Of course you could roll your own CA but then both parties need to trust it.