Sendmail messages rejected from Microsoft when using TLS

Welcome to Serverfault! :-)

Have you explicitly configured SendMail to use TLS? If not, out of the box, SendMail will still try to perform opportunistic TLS operations with a zero-byte client certificate. I assume this is what you're seeing? For more information on this (oddity?) check out @MadHatter's excellent response here: https://serverfault.com/a/514180/21875

So, with that said, I'll respond to your questions in the order they were asked:

1. Why is sendmail sending the client certificate to outlook.com as part of STARTTLS?

When two MTAs are attempting to establish a secure tunnel for STARTTLS, it's normal for them to negotiate security information and exchange public certificates so they can securely encrypt information to one another. If sendmail didn't provide a client certificate to outlook.com, the outlook.com mail servers wouldn't have a way to encrypt responses/acknowledgements back to sendmail.

2. Is there a way that I can prevent sendmail from sending client certificates to servers outside our domain, even if the server requests it? From the experiments I've done, outlook.com will accept the message if I simply ignore the certificate request and send the message.

You have a few options:

Option #1: Implement a per-server / per-domain exception rule. This can be done by adding Try_TLS:<broken.server> NO to your access table. It sounds like you're already doing this but it's important to note that the "broken.server" part can be an IP, MX record (microsoft-com.mail.protection.outlook.com), or partial MX record (outlook.com).

Option #2: Implement a bypass rule for all domains. This can be done by adding Try_TLS: NO to your access table (no need to specify IPs).

Technically, you could also hack the sendmail.mc file to prevent sendmail from checking for TLS capability at all. I wouldn't recommend doing this though since it requires delicate changes.

_{Transfer solution from question to answer section.}

For anyone who has this problem and can't figure it out, I found the root cause and solution.

I couldn't prevent the client certificate from getting sent to Microsoft so my only option was to find out why Microsoft was rejecting the server. When creating the certificate we were using a different server name than was presented in the ehlo. e.g. mx1.example.com in the helo and mx.example.com in the certificate. The mismatch was causing Microsoft to drop connections without explanation.