While recently helping a client setup an Exchange Hybrid, the cloud to on-premises mail flow was failing validation due to 454 4.7.5 Certificate Validation Failure.
The next step was to verify that the TlsCertificateName value was properly set on the send and receive connectors to match the certificate name, following these articles:
In this case, the TlsCertificateName was already set correctly to match the certificate name (the Hybrid Exchange Wizard does a good job at setting that correctly).
The next step was to enable Verbose logging on the on-premises receive connector so that we can get a better look at the error.
To save time, I restarted the “Microsoft Exchange Frontend Transport” service so that the logging would take effect sooner.
Then navigating to the log directory can be a bit tricky:
C:\Program Files\Microsoft\Exchange Server\v15\TransportRoles\Logs\FrontEnd\ProtocolLog\SmtpReceive
Opening up the file revealed a very helpful bit of information! The SSL Certificate that Microsoft Office 365 is presenting to the Exchange server for the TLS encrypted email is not a trusted root. How can this be?
To cut to the chase, the root cause was that the server had not had windows updates run in a LONG time and therefore was really far behind in its root certificates.
The least disruptive solution was to download the Office certificate chains from Microsoft (here) and install them on the on-premises Exchange Server. Then after restarting the “Microsoft Exchange Frontend Transport” service and waiting a few minutes, the validation was successful.