I've no idea what Outlook 2016 does, or what Windows 10 does. With Outlook 2011 on Mac, encryption
and decryption work fine.
Perhaps you should check your certificates to make sure everything matches expectations for Email Security/Key Encryption, like
- Key Usage
- Extended Key Usage
- DN
- Maybe SAN
It might be useful/helpful to look closely at your cert and at the offending email header, but that information would be privacy-sensitive, so I cannot suggest posting it here.
Also, Outlook may have problems with ECC keys and certs, in a weird way. Just so you are aware.