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).