It's the key exchange that's difficult. However, as the blog rightly points out, having companies sign their emails would be a massive step in the right direction. Every ordinary person uses an email service. If that email service handled the key exchange for those companies the it would be truly wonderful. It doesn't even need to be that difficult given that these companies almost certainly have certificates for their websites.
Then all the service provider has to do is put this nice message when delivering the email: "This email was not signed by the company that it claims to be sent from. Beware." Not in any way difficult for an ordinary person to understand.