Postfix: Verify all outgoing TLS connections are being established properly

Are you sitting behind a firewall?

If so, check if you are using the ESMTP inspect rule. Removing this rule from global_policy may help.

I compared your Postfix configuration with a working configuration, and noticed that your configuration is missing smtp_use_tls = yes.

According to this postfix mailing list post, smtp_* entries apply to your SMTP server as a sender, while entries starting smtpd_* apply to your SMTP server as a recipient. It seems that your problems are restricted to your SMTP server as a sender.

I also found this Postfix documentation, which states that smtp_use_tls is set to "no" by default.

So I'd suggest setting smtp_use_tls = yes, and see if that does anything. If not, perhaps other smtp_* settings might be the problem.

EDIT: smtp_use_tls should be overridden by smtp_tls_security_level in newer versions of Postfix. I notice you didn't mention your Postfix version, but this will probably only help if it's older than 2.3.

Removing ESMTP from Cisco firewall Global policy fixed it for us. ESMTP comes default enabled in Cisco firewall.