I wonder if some of the usability frustrations would be eased if people adopted the convention of having a secure-only email address, where the only email it accepts is encrypted email. It probably would be easy to set it to bounce/delete any non-encrypted email. Maybe only check it using a separate email client. Traffic would be low so searching wouldn't be such a hassle. Use your other email address for receiving insecure email (and tell everyone that by default, their email addresses are insecure).