Just to clarify, an external sender (when replying to an email your company ad previosuly sent) would receive this error message?
Do you have access to the SMTP logs? Is their mail server actually trying to send to an unknown domain in the "send to:" part of the tarnsaction (in which case the error is legitimate)?