Ubuntu – Postfix: Verify all outgoing TLS connections are being established properly

I have been tasked with setting up a Postfix server running on Ubuntu. Emails are sending through my relay and all seems well except for the fact that I cannot seem to get TLS to work with Gmail or other mail clients. For example, please see the TLS output of my main.cf file:

# TLS parameters

smtpd_tls_cert_file=/etc/ssl/certs/company.com.crt
smtpd_tls_key_file=/etc/ssl/private/company.com.key
smtpd_tls_CAfile=/etc/ssl/certs/gd_bundle.crt
smtp_tls_CApath=/etc/ssl/certs
smtpd_use_tls=yes
smtpd_tls_auth_only=yes
smtpd_tls_security_level=may
smtp_tls_security_level=may
smtp_tls_loglevel=1
smtpd_tls_loglevel=1
smtp_tls_note_starttls_offer=yes
smtpd_tls_session_cache_database=btree:${data_directory}/smtpd_scache
smtp_tls_session_cache_database=btree:${data_directory}/smtp_scache

# See /usr/share/doc/postfix/TLS_README.gz in the postfix-doc package for
# information on enabling SSL in the smtp client.

I have done the following through Telnet to verify STARTTLS:

Connected to localhost.
Escape character is '^]'.
220 prod-email.company.local ESMTP Postfix (Ubuntu)
EHLO localhost
250-prod-email.company.local
250-PIPELINING
250-SIZE 10240000
250-VRFY
250-ETRN
250-STARTTLS
250-ENHANCEDSTATUSCODES
250-8BITMIME
250-DSN
250 SMTPUTF8
STARTTLS
220 2.0.0 Ready to start TLS

I also see TLS establishing connections to many other relay/exchange servers in the logs (there are many more than these examples):

Nov  2 11:08:58 prod-email postfix/smtp[7864]: Trusted TLS connection established to mx2-us1.ppe-hosted.com[67.231.154.163]:25: TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)
Nov  2 11:22:23 prod-email postfix/smtp[8672]: Trusted TLS connection established to mail.relaissanmaurizio.it[194.209.228.112]:25: TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)
Nov  2 11:22:25 prod-email postfix/smtp[8689]: Trusted TLS connection established to mail.relaissanmaurizio.it[194.209.228.112]:25: TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)
Nov  2 11:31:06 prod-email postfix/smtp[8676]: Trusted TLS connection established to mx1-us1.ppe-hosted.com[148.163.129.50]:25: TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)
Nov  2 11:51:13 prod-email postfix/smtp[9165]: Trusted TLS connection established to mail.relaissanmaurizio.it[194.209.228.112]:25: TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)
Nov  2 11:51:15 prod-email postfix/smtp[9229]: Trusted TLS connection established to mail.relaissanmaurizio.it[194.209.228.112]:25: TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)

I am also seeing these strange logs in /var/log/mail.log for a particular customer:

454 4.7.0 Connection is not TLS encrypted. Recipient organization requires TLS.

How is this possible when it seems that I am offering TLS to be used on outgoing emails? At least it looks this way according to the above logs (TLS Connection Established).

My question is, why do I not see these TLS connections being established with Gmail's servers or the server in the example above? I still receive the little red padlock on received Gmails sent through this relay server saying it is not being encypted. And some of my mail is being deferred because it is saying that the connection is not TLS encrypted?

How can I verify that TLS is working correctly and that all outgoing emails are being encrypted with TLS to those that accept the TLS protocol?

Anyone's help is greatly appreciated.

Best Regards

EDIT:

 openssl s_client -connect localhost:25 -starttls smtp

 STARTTLS
 554 5.5.1 Error: TLS already active

Gives me no errors regarding my certificates.

Email headers for Gmail and Outlook also do not show TLS encryption.

I am at a loss…

UPDATE: I just attempted to get this working by updating the certificates being used (wildcard cert was expiring in December anyway), and TLS is still not working properly. Please help.

UPDATE: I also attempted to force TLS for gmail and got the following error:

TLS is required, but was not offered by host alt1.gmail-smtp-in.l.google.com[74.125.192.27]

Why wouldn't google offer TLS? I am confused…