Outlook not updating certificate

Question

Outlook is refusing to send an encrypted email to a recipient whose certificate recently expired. The recipient sent a signed email and I exported the certificate to a ".cer" file then updated their contact information with the new certificate. It now shows the active date as being current. Nevertheless Outlook is still saying the certificate is invalid.

How can I send encrypted email to the recipient? Updated question: What needs to be updated?

UPDATE

I kind of solved this problem, but do not understand why it worked and would still like an answer of what may have happened.

I tried clearing the SSL cache by going to Control Panel / Internet Options / Content / click "Clear SSL Cache" button. That did not work.

What did work was the following: get email from recipient with new certificate, click From field, click Add to Outlook Contents, when card comes up click the "Update" button. Since I had already updated the certificate (and deleted the old certificate) for this recipient, I do not undertand why this worked.