tl;dr - Need to resolve the "TLS negotiation failed with error AlgorithmMismatch" error for successful e-mail flow from Exchange 2007 to Exchange 2013.
Site 1: 2 Exchange 2013 CA servers, 2 Exchange 2013 MB servers, 2 Exchange 2007 CA servers, 2 Exchange 2007 MB servers
Site 2: 2 Exchange 2013 CA servers, 2 Exchange 2013 MB servers, 1 Exchange 2007 CA server, 1 Exchange 2007 MB server
All Exchange 2007 servers are running on Windows Server 2003 R2 x64. Exchange 2007 SP3 RU16.
All Exchange 2013 servers are running on Windows Server 2012 R2. Exchange 2013 CU8.
E-mail flow was working just fine, until the above error started. This only happens between the 2007 CA servers and the 2013 MB servers in site 1, and only sending from 2007 to 2013. There are no issues sending from 2013 to 2007, and between sites. The messages were stuck in Hub Version 15 queue in both 2007 CA servers. The error message on the Queue Viewer was:
"421 4.4.2 Connection dropped." Attempted failover to alternate host, but that did not succeed....
Took a whole day to track down the issue, and finally found the error message on both 2013 MB servers' Receive log.
What I tried so far:
Creating a new self-signed certificate on the 2013 MB servers
Importing and assigning the CA certificate on the 2013 MB servers
Creating a new scoped receive connector on the 2013 MB servers and added the 2007 CA servers
Disabling the TLS on the 2013 MB servers' receive connectors
Here's the relevant portion of the receive protocol log:
250-X-EXPS GSSAPI NTLM,
220 2.0.0 SMTP server ready,
,CN=EXCH13MB01,Certificate issuer name
,XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX,Certificate serial number
,EXCH13MB01;EXCH13MB01.xxxx.yyyy.com,Certificate alternate names
,TLS negotiation failed with error AlgorithmMismatch