This error is due to the recipient not having a Secure Email Certificate installed. You may only send encrypted emails when public keys have been exchanged. If the recipient has a Secure Email Certificate, you can exchange keys by sending a signed email. After the certificate has been imported by your email program, you will have the ability to send encrypted email to that recipient.
You cannot view encrypted messages without your private key. Be sure to backup your private key every time you back up your email messages.
If your email software has marked a certificate as damaged or invalid, the certificate has either been revoked, has expired, or has been tampered with. You should not trust any email messages which your software has marked as unsafe.
During the import process for a Secure Email Certificate, there is an option to Protect your Private Key by prompting for the corresponding password every time the certificate is used. If selected, then you will be prompted each time you use the certificate in Outlook.