To get your public key, the receiver has to send you a signed email. When you receive this email, add the sender as an Outlook contact.