The ones that can reply will already have your certificate (public key) stored in their address book.

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