Looks like the server is not able to deliver messages to gmail, for example.
The firewall is disabled, but I'm still getting this error:
Apr 3 16:42:39 ns215233 postfix/smtp[5846]: 24E156C1E5B9: to=<luis.filipe.domin
gues@gmail.com>, relay=none, delay=63, delays=0.06/0.01/63/0, dsn=4.4.1, status=
deferred (connect to gmail.com[209.85.229.19]:25: Connection timed out)