Everything seemed okay but email were not getting delivered. Logs showed me that smtp connections were timing out:
tail -f /var/log/mail.log May 3 12:28:10 postfix/smtp: connect to gmail-smtp-in.l.google.com[18.104.22.168]:25: Connection timed out May 3 12:28:10 postfix/smtp: connect to alt1.gmail-smtp-in.l.google.com[2800:3f0:4003:c00::1a]:25: Network is unreachable May 3 12:28:40 postfix/smtp: 4984C41A1E: to=<email@example.com>, relay=none, delay=3246, delays=3186/0.01/60/0, dsn=4.4.1, status=deferred (connect to alt2.gmail-smtp-in.l.google.com[2a00:1450:400b:c00::1a]:25: Network is unreachable)
However, I could ping any of above ip addresses just fine.
Next step was to see if ip address of my VPS was blacklisted in RBLs, I used https://mxtoolbox.com/blacklists.aspx. None of my ip addresses were in any black list.
Port 25 was open in firewall, both on server and in Lightsail’s networking UI.
After spending another hour or so troubleshooting, I found this thread: https://forums.aws.amazon.com/thread.jspa?threadID=316397. It seems AWS/Lightsail have recently started to throttle outgoing emails, but by throttling they meant completely blocking it. You need to open a support ticket to remove these limits here: https://console.aws.amazon.com/support/contacts?#/rdns-limits
So I submitted my request, hopefully, this will resolve the issue.