I have a customer with an Exchange 2003 server. They had two domain names in the box (domain-1.com and domain-2.com). The company spun off the domain-2 division which is now at a different location and has their own seperate server.
I have rebuilt the address books and ensured that all references in exchange to domain-2.com have been removed.
If domain-2.com sends an email to a user at domain-1 it gets there no problem. If a user at domain-1.com emails to a user at domain-2.com it failed with a mail account does not exist at the organization.