I had the same problem with a similar client I did some work for. What we ended up doing is creating a mailbox via cpanel for the account that was doing the sending. Even though this was never actually used to receive any email, the host then seemed to think it was good to go. I think that some hosts do this to avoid you spamming using email addresses they have no way of validating you actually own.

Try adding it as a mailbox via cpanel and see if that takes care of your issue.