Ssl – way to test a SSL certificate for a SMTP server

A couple of months ago, my company bought a Rapid SSL Certificate which supports until 256-bits cryptography and which is used both for communication between our mobile apps and our server and to send emails by our SMTP server, which is also inside our Windows Server 2012 R2. I correctly managed to install it by IIS 6 in a custom SMTP server. Everything seems to work fine but only a company associated with ours told us that our SMTP server cannot connect to their incoming email server because

the certificate we use could not be "compatible" with new SHA256 cryptography standards.

I don't know exactly what this means but I called our certificate provider and they assured us the certificate we bought is correct. Moreover, I am quite sure that company is wrong because our SMTP certificate is able to connect not only to Gmail accounts but also to many other incoming email servers using that certificate. And messages have always been correctly delivered. So, I don't know where and how to investigate for the problem.

Generally, our SMTP server is evoked by .NET web applications deployed on our server Windows 2012 R2 like the following:

IDMailer M = null;
M = (IDMailer)new IDMailer();
M.FromAddress = new IDVariant(v_VEMAILRESIDE).stringValue();
M.Subject = IDL.FormatMessage((new IDVariant("|1: manutenzione ODL |2")), v_VNOMERESIDEN, v_ODL).stringValue();
M.SetRelayServer((new IDVariant("www.ourserver.it")).stringValue(), (new IDVariant(25)).intValue(), (new IDVariant("username")).stringValue(), (new IDVariant("password")).stringValue(),(new IDVariant(-1)).booleanValue()); 
M.HTMLBody = new IDVariant(v_HTML_MESSAGE).stringValue();

As you can see, the IDMailer (from framework System.Net.Mail) is set both to use our server as relay and to use cryptography to connect to relay (last parameter).
Thus, I don't really know where to investigate for the problem or even whether the problem exists and is ours.

UPDATE

As suggested, I try to analyze the mail servers with this site using one of our customers email in order to test the secure connection to their incoming mail server.

This is a first summary report:

from which I got confirmation that their authoritative incoming mail server are the first two.
Then, this is the log of the first server (the one the second is
identical)

from which I understood the problem might be theirs, as

TLS in not an option on this server

I mean that it might be their server which do not support TLS. Thus, as our SMTP server exclusively works with a SSL certificate, then it cannot connect to their incoming mail server. Am I right or am I missing anything else?