Unable to send email to anywhere

I am having issues with sending email to any server. Whenever I send an email the mail ends up in the mail queue due to mail being “rejected” by other servers.

The errors I am receiving are as follows:

Feb 4 12:56:01 example postfix/smtp[16549]: connect to alt2.gmail-smtp-in.l.google.com[2607:f8b0:400c:c06::1a]:25: Connection timed out
Feb 4 12:56:01 example postfix/smtp[16549]: 99C5E7E904: to=MYEMAIL@DOMAIN, relay=none, delay=3484, delays=3334/0.02/150/0, dsn=4.4.1, status=deferred (connect to alt2.gmail-smtp-in.l.google.com[2607:f8b0:400c:c06::1a]:25: Connection timed out)

I have verified that I can connect to this server using telnet. Therefore I am confident to conclude that my connection is not being blocked by my ISP. I also currently have no firewall active while this issue persists.

I am running the latest virtualmin LEMP stack on a fully updated clean Debian 9 install.

What ports did you test with telnet?

I tested port 25, since that is the port that postfix is trying to use according to these logs. I tested telnet using this same server.

Did you try to test port 25 from your server to google? Pick any google IP you see from the logs and try to connect from your server. If is ok then the problem is probably miss-configured postfix, but if you cant connect then the problem could be your firewall or google banned your IP for some reason.