Also the current global status of TLS on incoming mail servers is a bit cahotic. A lot of service providers mail servers use deprecated TLS versions and some even doesn't handle new ones that are current standard.
So if the sender server only accept TLS 1.2 and 1.3 and the remote server only propose TLS 1.0 and 1.1 (or even older), they can't negotiate and the transaction fails.
If I remember correctly, in SmarterMail, when sending with TLS fails, it fallbacks or at least was falling back to Non-TLS for the next retry. Have you check your logs, when the mail is finally sent, is it in a TLS enabled session?
Also it can be that a provider has multiple MX and some are updated with latest TLS libs and some other not and then it depends on which one you connect with the round-robin lottery of MXs. That could be the reason why sometimes it works and sometimes not.
All this bring another problem, if it retries without TLS after a TLS failure. You can't guarantee to your customers that the mail will be sent over a secure connection, and we have some customers that prefers the mail not to be delivered and receive a bounce instead of transmitting anything clear text on the wire.
So with all of this, our outgoing gateway we can force per source domain or destination domain, what we want for TLS (Try to use, Do not use, Force use and reject if it's not possible).
That way we have a complete control about our outgoing SMTP stuff.