Getting "The remote certificate is invalid according to the validation procedure" when SMTP server has a valid certificate

The answer I have finally found is that the SMTP service on the server is not using the same certificate as https.

The diagnostic steps I had read here make the assumption they use the same certificate and every time I've tried this in the past they have done and the diagnostic steps are exactly what I've done to solve the problem several times.

In this case those steps didn't work because the certificates in use were different, and the possibility of this is something I had never come across.

The solution is either to export the actual certificate from the server and then install it as a trusted certificate on my machine, or to get a different valid/trusted certificate for the SMTP service on the server. That is currently with our IT department who administer the servers to decide which they want to do.

Old post but as you said "why is it not using the correct certificate" I would like to offer an way to find out which SSL certificate is used for SMTP (see here) which required openssl:

openssl s_client -connect exchange01.int.contoso.com:25 -starttls smtp

This will outline the used SSL certificate for the SMTP service. Based on what you see here you can replace the wrong certificate (like you already did) with a correct one (or trust the certificate manually).