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.