Bananas had tls setup badly* once on a postfix mail server and decided to fix it better, it worked inbound, but i had not bothered to do outbound.
I fiddle about and set
smtp_tls_note_starttls_offer = yes smtp_tls_security_level = may
smtpd_tls_mandatory_protocols = !SSLv2,!SSLv3,!TLSv1,!TLSv1.1
smtpd_tls_received_header = yes
smtp_tls_note_starttls_offer = yes
smtpd_tls_exclude_ciphers = aNULL, eNULL, EXPORT, DES, RC4, MD5, PSK, aECDH, EDH-DSS-DES-CBC3-SHA, EDH-RSA-DES-CDC3-SHA, KRB5-DE5, CBC3-SHA
Cipher.lst is helpfull here – As while i may have it, you cannot say 100% that everybody else can do it so enforce was out of the question due to a name mismatch on the certificate.
A Postfix upgrade (my blog) helped more.
* my blog it works but was not that usable.