E-Mail Routing Problem

I have had a single office in one location, but now my office is opening a new branch in another country.
I want to be able to route all the mail including that in the new branch using the same domain name.

I have a cisco router( 3600 series), i have been using sendmail on a linus server as my mail server and my ISP has been managing my DNS.
Can any one give advice now how i can set up the system to manage this.