After running HCW (Full Classic Hybrid + Centralized Mail Transport), the outbound communication between EXO to Exchange Server 2013 didn't work. Found the validation failed if we specified subject name (the wildcard certificate *.ourdomain.com) under "Always use TLS to secure the connection".
If we changed it to "Any digital Certificate", validation passed and mail started flowing.
The validation error is "4188.8.131.527 cannot connect to remote server [Message=SubjectMismatch]"
Has verified the same wildcard cert is bind to Default Frontend Receive Connector too and installed on Exchange 2013 (single server farm) too. Fortigate firewall forwards the traffic on port 25 directly to Exchange Server.
Also it is really odd not much relevant information has been logged in the receive connector log.