So, I had this exact issue and now the mystery (for me anyway) is somewhat solved, but a work-around for Office365 or Exchange mailboxes still remains. Everything worked perfectly (albeit cumbersome to setup) and then broke as soon as I upgraded iOS. I have two mail accounts on my iOS mail app (iCloud & Exchange/O365). Installing the certificates worked great. Enabling S/MIME signing, and encryption was buried but pretty easy. Although for this post all I want to discuss in "signing" not encrypting, because the problem emerged with signing, so forget encryption if signing is not working yet.
Getting my iCloud account to sign (and encrypt) email was accomplished after sending myself a signed email, and installing my own public key associated with my own contact in my contact list. The problem started when I added my second mail account which happens to be O365/Exchange. Network packet captures showed that although I was attempting to sign emails to/from iCloud only accounts, the mail client was sending OCS packets/sessions across SSL/443 to O365 servers for validation/verification. Let me repeat; even though the ONLY emails involved were Apple iCloud accounts, the OCS certificate validation (the step that occurs when attempting to sign) was attempting to validate using the WRONG servers (Microsoft). It was doing this because I had an O365 profile loaded (my work account) but this was overwriting the process for my iCloud profile as default.
To make the issue even more problematic (other than the wrong servers attempting to be leveraged for OCS validation), Microsoft actually has an issue supporting S/MIME on certain O365 mail accounts. Their "auto-discovery" protocol for detecting what kind of endpoints (mail client apps) are connecting to O365, detect if you're an "Outlook App" client or leveraging something else (like iOS Mail App). If you're sending/receiving email from O365 mailboxes, while using a mobile device with Outlook app, Microsoft will email you letting you know they "DO NOT SUPPORT S/MIME OR ENCRYPTION ON THIS MAILBOX." Here's the article, and looming patch hopefully in the future.
So sorry for muddying the waters a bit more, but this is a combination of issues ranging from iOS Mail detecting and leveraging the wrong OCS servers because of multiple mail accounts loaded, as well as O365 not fully supporting S/MIME on all devices as of yet.
If anyone has further details please post :-)
-Justin