When checking their configurations, everything seemed at first to be in order. Upon checking into it further, I noticed that their mail FQDN is mail.domain.com, but it looks like the common name on the certificate is just domain.com (though mail.domain.com was also on the cert under the subject alternative names). While the cert was registered as valid, it did not match up for the mutually authenticated session. The problem? The red outlined boxes didn't match up.
After changing the principal name to msstd:domain.com rather than msstd:mail.domain.com such that it matched the certificate name, the authentication began to work once again.