And the preference didn't show up in the prefs screen.

This patch doesn't work. There are undefined variables ($prefs), empty 
objects ($recip['list']), empty notifications...
Please test your patch again against a clean checkout of the master branch.

Hm, I guess it's a trade-off between 1) putting the new encryption 
option to the existing encryption options instead of "hiding" it in 
the prefs, and 2) cluttering the encryption list even more, especially 
if this gets implemented in PGP too.
Let's try it the way you implemented it and wait for user feedback. 
Unless someone has further objections?

No particular reason, it would just be slightly more complicated. I 
don't know if enumerating additional "Automatic" variants of 
'smime_encrypt' and 'smime_signenc' is a good idea. Additionally, it 
only supports S/MIME. The current approach could be adapted to support 
PGP and the checkbox moved from S/MIME preferences to the Composition 
preferences.

Looks very good. Any special reason not to make this a new option of 
the encryptselect/default_encrypt preferences?

I've attached an updated patch that satisfies the discussed 
requirements. Existing functionality changes only when automatic 
S/MIME encryption is enabled in the S/MIME preference group.

If public keys for all recipients are found, the message will 
automatically be encrypted before being sent. Otherwise, the user will 
be notified of the recipients for which a public key could not be 
found. This notification will occur only one time, unless the user 
adds additional recipients for which public keys can't be found, in 
which case the user will be again notified. The notification is 
identical to the one used for detecting missing attachments.

Let me know what you think. This patch is actually pretty simple and 
applies cleanly.

Sure, the check in line 39 ensures that encryption is *not* already 
enabled before attempting automatic encryption. Line 55 ensures that 
if S/MIME signing is enabled it remains enabled in addition to 
encryption.

I'm happy to contribute the remainder of the patch but I'm not sure 
how to best implement either option for notifying the user. I also 
posted on the dev mailing list for tips. Thanks!

The if-clause in line 55 of your patch doesn't make sense because it 
can never be true, see the check in 39.

This is a great start, thanks a lot! To be applied we would need at 
least one of the two suggested solution for notifying about missing 
encryption keys for certain recipients.

I've attached a patch to 96f00a to get started on this enhancement. 
I'm also able to submit a pull request on Github if it helps. I'm 
hoping this will help move this enhancement along as we'd love to see 
it deployed!

We will soon be releasing a plugin (hook) for IMP that allows users to 
automatically retrieve certificates for message recipients using DANE 
SMIMEA (https://tools.ietf.org/html/draft-ietf-dane-smime-14). 
Enabling automatic/opportunistic S/MIME encryption makes this feature 
very useful.

Sounds both good.

Now that IMP has it's own autocompleter, maybe another option would be 
to maybe tie in the public key lookup with the autocompleter, showing 
a small lock icon or similar in the recipient bubble when a key is 
found? Similar to what iOS does.

Currently, there are two ways how to enable S/MIME encryption:
1.) Set is as default.
2.) Enable it by hand for every message which needs to be encrypted.

No one of it is perfect:
1.) You need to disable it by hand for every recipient without public 
key installed. Otherwise the IMP refuse to send e-mail.
2.) There is a pretty high chance that sooner of later you will simply 
forget to enable it and private data will be send and saved in clear 
text.

I suggest to create a new type of S/MIME encryption settings:
3.) Encrypt every message automatically when public key of all 
recipients is available. Display a warning  message (OK/Cancel) if 
public key of only part of recipients is available.