Mail delivery error and SSL

We recently enabled SSL at the request of one of our customers. We are using negotiated SSL which seems to be working well except for one other customer. When we attempt to send mail to the second customer, we get the follwowing delivery failure message “SMTP Protocol Returned a Permanent Error 503 5.7.0 Authentication required”. I thought that negotiated SSL meant that if the receiving server doesn’t support SSL, Domino will simply send the email without using SSL. Any suggestions/recommendations would be appreciated. Thanks.