Se for um email para um usuário interno (mesmo domínio), a chave pública do destinatário (usada para criptografar para esse usuário) é armazenada na GAL.
Se não houver problemas de conectividade, o Outlook mobile deve conseguir entrar em contato com o Exchange silenciosamente e isso deve ser resolvido em segundo plano.
Se for um usuário externo (domínio diferente), a chave pública do destinatário (usada para criptografar para esse usuário) pode ser obtida trocando um email assinado com esse destinatário.
Depois de trocar emails assinados e instalar o certificado, você poderá enviar emails criptografados.
Se você não conseguir criptografar, está faltando a chave pública do destinatário.