Brian,
Had an Exchange 2007SP3RU10 server. 120 users with 180 mailboxes. Installed Exchange 2013CU2 in the organization. After migrating a test mailbox to the new Exchange 2013 server we noticed that the test user could not send back to the Exchange 2007 server. The Exchange user could send and receive from the Internet (via the send connector on the Exchange 2013 server and the Internet receive connector on the Exchange 2007). The Exchange user could not send e-mail to any user on the Exchange 2007 system.
Being off-hours and a scheduled window, we switched the mail-flow at the firewall NAT to route incoming to the new Exchange 2013 server. We determined that if a mailbox was on the Exchange 2013 system, mail flowed fine. We determined at that point to switch the mail flow during the user migration window in order to resolve.
After the migration we powered down the Exchange 2007 server to verify. I spun the server back up and created a test mailbox on the 2007 side. I could not send an e-mail from a 2013 user back to the 2007 mailbox...but the 2007 test mailbox could send fine including to and from the Internet. I then created new receive connectors on both the 2007 server as well as the 2013 server. I allowed anonymous and added the exchange server as the source. Wham. Mail started flowing and the queue emptied.
At that point I decided to bag it...and we finalized the uninstallation of the 2007 server and just called it quits. That's really all there was. Rebooting the servers didn't help. I'm almost curious if it had something to do with IPv4 or IPv6 issues...but again, it's impossible to troubleshoot IP-related problems now with the new Exchange development model that throws out traditional TCP/IP.
If you read the technet forums link I sent you'll see there are a few others who had pretty much the same symptoms I had. We also had some very strange behavior with the certificates as well. Pop was assigned to a "mail.company.com" SAN certificate, yet the Pop clients were getting the NetBios server certificate instead and security was failing. The timeout in the config file was really problematic. What was scheduled for a 4 hour move window (since we'd used the suspendwhenready option) turned into a 24+ hour problem very quickly.