Postfix - Untrusted TLS connection

My server is running on Ubuntu 16.04 and Postfix is installed. All the emails sent from my server are marked as spam by Gmail and I thought that setting up a TLS/SSL certificate from Let’s Encrypt might help. Having generated a certificate (by command: sudo letsencrypt certonly --agree-tos --email [email protected] -d mail.my-domain.com) and added basic Postfix configuration, I receive logs with a message (while sending emails):

postfix/smtp[337]: Untrusted TLS connection established to gmail-smtp-in.l.google.com[64.233.163.26]:25: TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)

I added this to /etc/postfix/master.cf:

submission inet n       -       y       -       -       smtpd
 -o syslog_name=postfix/submission
 -o smtpd_tls_security_level=encrypt
 -o smtpd_tls_wrappermode=no
 -o smtpd_sasl_auth_enable=yes
 -o smtpd_relay_restrictions=permit_sasl_authenticated,reject
 -o smtpd_recipient_restrictions=permit_mynetworks,permit_sasl_authenticated,reject
 -o smtpd_sasl_type=dovecot
 -o smtpd_sasl_path=private/auth

And to /etc/postfix/main.cf:

# TLS parameters
smtpd_tls_cert_file=/etc/letsencrypt/live/mail.my-domain.com/fullchain.pem
smtpd_tls_key_file=/etc/letsencrypt/live/mail.my-domain.com/privkey.pem
smtpd_use_tls=yes
smtp_tls_security_level = may
smtp_tls_loglevel = 1
smtpd_tls_loglevel = 1
smtpd_tls_session_cache_database = btree:${data_directory}/smtpd_scache
smtp_tls_session_cache_database = btree:${data_directory}/smtp_scache
smtpd_tls_security_level=may
smtpd_tls_protocols = !SSLv2, !SSLv3

Is there an easy way to gain a Trusted TLS connection instead of untrusted, do I need to buy something or this free certificate should work? And does it actually affect deliverability of my emails? I have really read a lot concerning 'spam topic' on this forum, but nothing helps.

Is there an easy way to gain a Trusted TLS connection instead of untrusted, do I need to buy something or this free certificate should work?

This is not about your certificate, so you don't need to buy anything. It's about: How does your Postfix verify the cert of Gmail?

Try to add:

smtp_tls_CApath = /etc/ssl/certs
smtpd_tls_CApath = /etc/ssl/certs

to /etc/postfix/main.cf.

And does it actually affect deliverability of my emails?

Not really. Check your setup for DNS records (remember PTR as well), DKIM, SPF, etc.