From what you are describing, it definately sounds like a misconfiguration on the sending companys side. If they are getting authentication errors sending outbound mail, then they have something configured wrong.
Even if they tried to send directly to your client's mail server, they would not get that error as they would be sending to a local mail address at that point.