Exchange mail flow not working? Check your (Cisco) firewall!
I’ve come across this issue several times: External mail (or mail between Exchange servers) cannot be delivered, however when you check with telnet the Exchange server(s) are responding. When you check via telnet on the external IP you get something similar:
In this case it was a Cisco ASA firewall that had (E)SMTP filtering feature (also called Mailguard) enabled, which is the default setting.
The feature also blocks SMTP TLS connections, which is used in Exchange hybrid configurations which uses Strict TLS for mail flow between on-premises servers and Office 365.
To resolve this issue, disable the (E)SMTP filtering feature on any device that in some way handles SMTP traffic (don’t forget those in between Exchange sites of your organization!). That’s it!
/edit 20140707:My coworker PaulM provided me with an screenshot on how to disable this feature. Thanks!
Configuration > Firewall > Service Policy Rules > Default inspection policy: