Unable to connect to Exchange 2010 mailbox

I'm having an extremely hard time trying to get SDP connect to the mailbox. The credentials to access the mailbox are correct.

SDP keeps showing this error:

FAILURE :E-mail settings saved successfully. But error occurred while trying to check connection with mail server - Problem connecting to mailbox.

I'm seeing this event ID 12014 on the Exchange 2010 server:

Microsoft Exchange could not find a certificate that contains the domain name mail.fqdn.domain in the personal store on the local computer. Therefore, it is unable to support the STARTTLS SMTP verb for the connector Internal Relay with a FQDN parameter of mail.fqdn.domain. If the connector's FQDN is not specified, the computer's FQDN is used. Verify the connector configuration and the installed certificates to make sure that there is a certificate with a domain name for that FQDN. If this certificate exists, run Enable-ExchangeCertificate -Services SMTP to make sure that the Microsoft Exchange Transport service has access to the certificate key.

Support engineers have told me that I would nee to enable clear text authentication in order for SDP to work, which we can't do due to security risks.

Any idea how I can get this to work without making any security changes to our Exchange server?

Outlook clients and owa are working perfectly fine.

Thanks!

(Exchange noob)