Getting a The e-mail account does not exist at the organization this mess

We have a Windows SBS 2003 server using exchange to pop our email for our branch. We are thye only branch to use a server running exchange. Our company pops all email from one provider, our Exchange pops it for us. We send and receive ok except when we send to other branches pop accounts. We all share the same host name ie user@123abc.com. We get a message stating “The e-mail account does not exist at the organization this message was sent to. Check the e-mail address, or contact the recipient directly to find out the correct address.” We know this is a valid email address, so how do we solve this?