Probably shows as invalid:
Get-ExchangeCertificate
Looks like you are not importing the private key.
Remove the one that isnt working from the 2016 Server, then:
The easiest way to fix is to export the cert from the 2010 servers with the private key and password to a *.pfx file.
Then import that to the 2016 servers
Ensure that the complete cert chain is installed on the 2016 servers as well.
You can verify:
https://www.digicert.com/support/tools/certificate-utility-for-windows