"Your DigitalID cannot be found in the underlying security system." outlook

I have a user that can send encrypted and signed emails. The user can read signed emails but not encrypted emails. This is the error received. “Your DigitalID cannot be found in the underlying security system.”

When I look at Certmgr.msc Other People>Certificates, I see his certificate and the correct expiration date. I went as far as to revoke his certificate and get him a new one.
I have never seen this issue before since I have setup many certs previously.