In order to exchange encrypted e-mails with someone, you have to exchange your public keys. A public key is part of a Digital ID and you can exchange it with your recipient through e-mail or in person.
This will allow you to have encrypted conversations, ensuring that both your e-mails and those you receive are sent by the right person. The public key is included in a tamper proof document called digital certificate. Inside a trust domain (e.g., in an enterprise that has deployed a PKI infrastructure), the certificates should be published in the enterprise directory and the e-mail client should be able to get them automatically,
Otherwise, to obtain the certificate of your correspondent , you should ask him/her to send you a signed e-mail, as Outlook will attach the sender certificates to the e-mail. Normally, you should then verify that this is the right certificate by calling the certificate and verifying that the certificate "thumbprint" is correct. If you are using PGP, there are public repository for the certificates such as the M.I.T. directory available at http://pgp.mit.edu/.