TLS not available: connect timed out

Hello,

One of our users forwarded the following bounce-back to me:

--- CUT HERE ---
<user@domain.tld>:
TLS not available: connect timed out
I'm not going to try again; this message has been in the queue too long.
--- CUT HERE ---

NOTE: 'user@domain.tld' has been used in place of the actual email address
the message was trying to be delivered to.

What I believe this means is that the MX server for 'domain.tld' is
advertising that it supports TLS (it does, as I checked by telnetting to it,
and issuing a 'EHLO localhost' on it), and so my Qmail server tried to
communicate using that protocol, but something is not configured properly
somewhere.

My question is: is the configuration error on my side or theirs? I am
pretty sure I do not have a certificate generated on my server, but I was
pretty sure that it was only necessary if I support/enable TLS connection to
my server, which I don't on that server (our SMTP server is not the MX
server for the domains we host). I am almost sure it is their side, but
just wanted to make sure.

TIA for your assistance.

Alan Murrell