Error in trying to encrypt mail in O365

Have you exchanged signed emails with that person previously? Are the certificates published in AD/GAL? The way SMIME encryption works, you need to have the recipient's Public key before you can send encrypted mail. So you either need to have received the key previously (via signed message, so it's stored in Outlook now) or have it published in a central location (AD/GAL).

Read more here: https://technet.microsoft.com/en-us/library/aa995740(v=exchg.65).aspx

To configure SMIME in ExO: https://blogs.technet.microsoft.com/exchange/2014/12/15/how-to-configure-smime-in-office-365/