Microsoft doesn't allow sending public-key encrypted messages using Outlook 2003-2012 on Windows 7-8x environments without first creating your own Digital ID or private key for signing.
Per Microsoft, before encrypting an email to someone else, "it is required that both parties have valid digital certificates for email signing and encryption at the first place." Why? If I have someone's public key, why do I need to have my own - valid or invalid - certificate? I am not signing the message, just encrypting it so that only the recipient can read it.