Outlook 2016 Email encryption issue

I have multiple users that when trying to send an email encrypted they get the error following recipients had missing or invalid certificates, or conflicting or unsupported encryption capabilities.  One of the users is me however some users can send me encrypted emails.

If the person sending the encrypted emails search for me , right clicks , and adds me to his contact list he then is able to send me an encrypted email. I know this is not normal they should just be able to click reply with out adding me into contacts.

Any ideas?
Michael MillerAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

David Johnson, CD, MVPRetiredCommented:
to send s/mime encrypted mail you need the recipients public key and the recipients need your public key
David FavorLinux/LXD/WordPress/Hosting SavantCommented:
Reading your question my first thought was S/MIME as David Johnson suggested.

And maybe I'm guessing incorrectly.

Let's be clear if you're talking about....

1) True message encryption, as David Johnson suggested.

2) Opportunistic TLS which encrypts SMTP connections.

Mention which of these are correct.
Michael MillerAuthor Commented:
Yes you are both correct.

However users get the error : Microsoft Outlook had problems encrypting this message because the following recipients had missing or invalid certificates, or conflicting or unsupported encryption capabilities.

If you go to the address book , right click on the user in the address book  and choose to add to contacts. In the contact you can see the user has certs published. if you choose to Save and close ( adding the user to your contacts) the error message goes away and they are able to send the encrypted email to the user.

This is only for a few users not all users are affected.

It is something in the network?

Thank you
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.