Recently I ran the Hybrid Configuration Wizard in an Exchange 2016 and Exchange 2019 environment. There were also two Edge Transport servers in this environment. One Exchange 2016 CU12 Edge Transport server is used for internet communication, one Exchange 2019 CU1 Edge Transport server (running on Windows 2019 Server Core) is used for hybrid communication. This server was selected in the Hybrid Configuration Wizard, proper certificate was selected etc. and the Hybrid Configuration Wizard finished successfully.

When the wizard finished the Receive Connector on the Edge Transport server was modified for hybrid mail flow. Validating the Send Connector from Exchange Online to Exchange on-premises revealed no issues, the test message was successfully sent and received in my mailbox.

But message flow from Exchange on-premises to Exchange Online was not working and mail was stuck in the Queue on the Edge Transport server. Looking at the Queue it seems there’s a time-out issue since it says:

LastError : [{LED=451 4.4.395 Target host responded with error. -> 421 4.4.1 Connection timed out};{MSG=};{FQDN=exchangelabsnl-mail-onmicrosoft-com.mail.protection.outlook.com}; {IP=104.47.10.36};{LRT=5/2/2019 6:32:14 AM}]

It is not a firewall issue, I can use Telnet to connect on port 25 and send a message to myself (which arrives in the junk mail folder, but it arrives).

Opening the Send Connector protocollog file (enable in on the outbound connector first) shows a different error. When trying to execute the TLS handshake it fails with TLS negotiation failed with error NoCredentials.

This is strange since the same certificate is used by the Receive Connector (you can check this using https://checktls.com and entering the FQDN of the Exchange server holding the Receive Connector).

The “TLS negotiation failed with error NoCredentials” looks like a private key issue with the certificate (according to Microsoft kb article KB4495258) but PowerShell shows it does have a private key:

When going back to the protocol logfile you can see the certificate thumbprint in the data field, and this thumbprint didn’t match the thumbprint of the certificate that Get-ExchangeCertificate returned.

But, Get-ExchangeCertificate only returns certificates that have a private key, if there isn’t a private key nothing is returned.

When opening the certificate store using PowerShell using the following commands:

CD Cert:
Cd LocalMachine
Set-Location my
Get-ChildItem

All certificates in the store are shown, and when checking the certificate with the thumbprint we got from the protocol log, this one does not have a private key:

That explains the NoCredentials error messages. Use the following command to remove the wrong certificate:

Get-ChildItem | ?{$_.Thumbprint -like “B79*”} | Remove-Item

After restarting the Transport service cross-premises mail flow works again.

The main question is of course how this happened. I’m not sure, but I do remember requesting several certificates at the same time (a few weeks ago) and there were a few errors. I didn’t pay too much attention to this since everything seemed to work fine. But in the end it turned out to be not the case, and I didn’t notice in the first place because of inbound SMTP working fine. Sigh…. 😊