Whenever mail is sent, there should be some indication of whether it's going to be encrypted. This indication should not get in the way of normal use. In particular, it shouldn't be worded so strongly it scares users away from the product. Suggested colors are green for encrypted, yellow for unencrypted.
Clients keep a database which maps email addresses to public keys. Whenever a piece of mail is received, the entry for the From: address is overridden with the information in the X-Envelope-Mail-Info field. If there is no such field, the entry is removed completely. This way, if a user ever changes to a mail client which doesn't support Envelope Mail, they can respond to encrypted messages requesting the information be sent again and the next message will be plaintext. Also, if a user changes to a new client but doesn't copy their keys over they will still get decryptable responses to new messages.
If the From: address and the sender given in X-Envelope-Mail-Info are inconsistent, that's treated as having no X-Envelope-Mail-Info field at all. This prevents erroneous encryption of messages to mailing lists.
Mail with a Cc: or Bcc: line is sent plaintext. It might be reasonable to split it into multiple messages on the client, but this is the safe and easy thing to do.
As long as there is only one recipient, outgoing mail is encrypted whenever possible. It is encrypted for both the sender and recipient. The key used for the sender is the 'preferred' one included in all outgoing mail.
When a client gets an encrypted message, it tries to decrypt it using all the private keys it has. If none work, it simply displays the message raw.
Encrypted messages are sent as mimetype multipart/alternative, with one alternative text/plain which includes an explanation of Envelope Mail and help information in case something can't be decrypted, and the other alternative encrypted/envelopemail, which contains the ciphertext. The ciphertext decrypts to a complete piece of mail, including headers.
The user should be able to manually remove stored information for sending to a specific email address.
When plaintext mail is displayed, the Message-ID header tacked onto the ciphertext is displayed along with the original headers.
When first installed, a client should pick a random new private key.
There should be a way of getting a list of all keys the client has stored, adding new ones, and selecting which is the 'preferred' one specified in outgoing mail. This way it's easy to copy keys over later if you had to start using a new client while the old one was unavailable or out of commission.
Keys are displayed and entered as described in key encoding.
And, of course, it should be easy to install and uninstall Envelope Mail functionality.