Contacts: Retrieve user certificate
As the title says, it seems Evolution is not able to retrieve S/MIME certificates from Exchange. The certificates are definitely there, as Outlook is able to retrieve and use them. Receiving a signed email from someone causes their certificate to be cached by Evolution, after which S/MIME encryption works just fine. However, if a recipient's certificate is not yet known to Evolution, the following message is shown when trying to send an encrypted email:
Could not create message. You may need to select different mail options. Detailed error: Cannot find certificate for “email@example.com”