Sendmail with SSL/TLS does not work properly with FIPS-enabled servers

Issue

• We have a mail setup using Sendmail already working.
• We wish to start using SSL/TLS in order to strengthen our security.
• All our servers are FIPS-enabled/compliant.
• However, when trying to do a starttls session we get the following error on our mail server's logs:

Apr 23 16:18:48 server sendmail[19587]: s3NKIlZQ019585: to=<user@example.com>, delay=00:00:01, xdelay=00:00:00, mailer=esmtp, pri=120447, relay=mail.example.com. [66.205.80.69], dsn=4.0.0, stat=Deferred: 403 4.7.0 TLS handshake failed.