I am stumped by an email encryption issue in Outlook 2010.  A couple of weeks ago I setup a new employee with email encryption using a new certificate requested from our CA.  After setting up email encryption for the user he was able to send and receive encrypted emails.

However, when he receives an encrypted email from a specific user and attempts to open the message he gets, "Your digital ID name cannot be found by the underlying security system."

Prior to this, every time I've seen that message it has been caused by the recipient having an expired certificate.  But in this case, the recipient is a new employee that never had an encryption certificate before, and the certificate he is using now is new.  Also, since the recipient can send and receive encrypted messages with other employees, we know that certificate is good.

The article below states that this message can occur when, "The sender of an encrypted message uses a Public Key for the recipient that is not installed on the recipient's computer (such as an expired Digital ID)."  One of the recommended solutions is to verify that the sender has the correct public key for the recipient.  I can see how that would apply for a recipient who has had an expired certificate.  But since this recipient is a new employee and has only had one certificate, which is currently valid, I don't see how the sender could have an incorrect public key for the recipient.

http://support.microsoft.com/kb/258527

I feel like somehow the issue is on the sender's end, but I don't know what to look at next in order to resolve this issue.  Also, I'm not sure how I would go about verifying that the sender has the correct public key for the recipient.  Any ideas?

Thanks for any help that you can provide.

--Tom