Deciphering TLS Issues within Exchange

What do you do when you suspect that there is an encryption problem preventing mail delivery? Identifying these types of issues is usually pretty easy. You add the domain to your TLS exempted send connector's scope and the mail delivers; remove it and it fails. Unfortunately, getting the details as to why it fails is many times far more difficult than it should be.
Circumstantial evidence is often your friend in these situations. Think about it, if you are able to send messages via TLS to one organization and not to another, the chances are that you are not the organization with the problem.

Certificate Expired

An expired certificate on one side or the other is far and away the number one reason TLS suddenly stops working. Checking servers in your charge is relatively simple using the certificate manager MMC plug-in or the Get-Exchangecertificate powershell command. You should also see an Event ID 12016 at connector startup indicating the certificate has expired. (And a period of time where you were getting Events of ID 12018 telling you the certificate is about to expire) If you do end up renewing the certificates for your exchange transports, make sure to run the enable-exchangecertificate powershell command again to instruct exchange to begin using the new certificate as it will not do it automatically.
Finding and proving that a 3^rd party's servers have expired TLS certificates is a little trickier. If the 3^rd party domain lands in your "opportunistic TLS" connector, mail will still flow; it will simply be sent via normal SMTP without any encryption. If you look in the SMTP logs for messages to that domain, you will see an error similar to the following:

A secure connection to domain-secured domain 'example.com' on connector 'Default external mail' could not be established because the validation of the Transport Layer Security (TLS) certificate for Example.com failed with status 'Expired. Contact the administrator of ourclient.com to resolve the problem, or remove the domain from the domain-secured list.

If the 3^rd party domain lands in your "TLS required" connector, mail will not flow any longer and again you will see errors in the SMTP logs
Now if you are like most and the notion of digging through mounds and mounds of SMTP logs sends shivers up your spine, you can use OpenSSL to assist in the process (Windows binaries available here). Simply run openssl s_client -connect mail.example.com:25 -starttls smtp
Any irregularities in the client's certificate will be reported in the results.
Unfortunately, using the Windows binaries your client will fail the verification portion of the tests as it cannot look into the local certificate store to pull your certificate.

Wrong Certificate in Use

With Exchange's use of self-signed certificates for internal communications, it is a simple matter for an organization to inadvertently use the wrong certificate for its public TLS encryption. Checking your own servers is simply a matter of using the Get-Exchangecertificate powershell command to verify that the proper certificate is selected for use on your public send and receive connectors. Pay special attention to the thumbprints as many organizations have failed to run the enable-exchangecertificate powershell command again after renewing their TLS certificates resulting in the legacy certificate still being used even though a newer (and valid) certificate is available.
For checking 3^rd party servers, I know of no better tool than the method using the OpenSSL tool described above.

Getting Mail Delivered

If it is your servers with the issues, taking the steps above should help you correct any certificate issues quickly. (at least as quickly as your CA can provide) You obviously can't change the message security policy for your partners, but you can lessen the attention on your domain by simply changing the routing rules within your organization so that all domains leave your "No TLS" send connector and come in a receive connector that does not respond to TLS. This will help for all organizations except those that actively require TLS.
For situations where it is the 3^rd party server with the problem, simply move that domain to connectors that don't require TLS, assuming you don't have a policy prohibiting it, and notify their administrators.