Email recieving problem after moving to new loaction and server

Our office was hosting 2 email domains on our server. So *@domain@.com and *@domain.com. The users from domain B moved to their own office and their own server. I removed all accounts from domain B from the original server. For all the users at the office at domain A I had to go into their Outlook and also delete the addresses from the Outlook History (nk2 file) because they were erroring out it must cache the path to the local server. Anyway email between the 2 offices is working. However the users at the new location at domain.com report not receiving  a lot of client emails from outside. They have talked to a few and talked to them through typing in their same address manually but I can't do that for all their potential customers. The MX records have been updated for the new domain and if I send an email to the address at domain B it works but they are not receiving a lot of client email. What can I do to fix this?