You can only encrypt emails to someone else using their email (Digital ID) certificate (public key).
And, to do this their certificate (Digital ID) must be stored in your address book.

To add the certificate to an address book in Outlook right-click on the email address and select 'Add to Outlook Contacts'.

Then save that entry.