Too much is getting grafted onto the existing protocol
There's so many little pieces, with spotty support. We need a fresh start where everything is mandatory, with a new MXX record in secure/encrypted DNS (can't use it with standard DNS) that includes certificates etc. to fully handle the "prove your domain is who it claims".
It would use a different protocol than SMTP - might be something very similar like XRECV or whatever so you don't need to rewrite from scratch, but it is important that it can't be used with old clients. Every email would be encrypted with the public key of the recipient, and signed with the private key of the sender (oh no, this will make mailing to 1000s of people inefficient, boo hoo cry me a river, mailing lists can keep using the old technology) The mail server would have a new daemon that basically acted as a directory service to get the public key of a sender/receiver for validation/decryption. The keys would be good for a short period of time like a week/month, and automatically re-fetched when needed or regenerated when yours expired.
Two factor authentication would be mandatory. Everyone has a smartphone now, a simple app on a smartphone could generate the OTP to go along with your password (which wouldn't need to be impossible to remember now that you have that second factor protecting you, which would increase its acceptance)
So how do you convert from the old to the new system? Well, your clients would have a way of marking recipients as "MXX capable" or not, and every time you sent an email that was going to be sent via the old way, you'd get a pop up telling you who is getting it the old way. The default would be to NOT send to them (to avoid people simply hitting return and ignoring) and hopefully people with the new clients could help evangelize the laggards into conforming.
OK, I'm sure I've left a half dozen issues unaccounted for, but that's a pretty good start for five minutes thought I think!