sendmail reject=403 4.7.0 TLS handshake failed errors in Red Hat Enterprise Linux 6

Issue

• We are receiving TLS handshake errors on several servers.

Mar  4 15:52:54 testmachine sendmail[14046]: STARTTLS=client, error: connect failed=-1, SSL_error=1, errno=0, retry=-1
Mar  4 15:52:54 testmachine sendmail[14046]: STARTTLS=client: 14046:error:14092105:SSL routines:SSL3_GET_SERVER_HELLO:wrong cipher returned:s3_clnt.c:955:
Mar  4 15:52:54 testmachine sendmail[14046]: ruleset=tls_server, arg1=SOFTWARE, relay=smtp.example.com, reject=403 4.7.0 TLS handshake failed.

• A mail sent by mailx command is transfered to the sendmail daemon in localhost, and then it's sent to a relay server with TLS connection.
• The relay server is 3rd party mail server, and the local machine is Red Hat Enterprise Linux 6.