If it's an email to an internal user (same domain), the recipient's public key (used to encrypt to that user) is stored in the GAL.
If there are no connectivity issues, Outlook mobile should be able to reach out to Exchange silently and this should be resolved in the background.
If it's an external user (different domain), the recipient's public key (used to encrypt to that user) can be obtained by exchanging a signed email with that recipient.
Once you exchange signed mail and install the certificate, you will be able to send encrypted emails.
If you can't encrypt, you are missing the recipient's public key.
