It sounds like you've already figured it out.

You were requiring TLSv1.2 but some other remote mail systems didn't support it and were unable to fallback and, as a result, couldn't negotiate a secure connection.

Or did I miss something?