In spite of correct DNS, Exchange sending to wrong destination server for single outbound domain

Howewer you configure it, Exchange is not going to route a message outside the organization if the destination address belongs to someone in Active Directory. Whenever Exchange needs to route a message, the first step it tries is always to look for the destination address in AD, and only after this fails it will choose a proper external routing path, based on the connectors you define.

With Exchange 2007 you can have "shared" SMTP domains, i.e. domains for which some addresses may be managed by Exchange, and some other by another system (in a coexistence scenario); I don't know if/how this is possible with 2003, but even if it was, the above stated golden rule still applies: first thing first, Exchange will try to deliver the message internally, and only if it can't, it will send the message outbound.

Think about it: if there was a way to do what you ask, what would Exchange do when receiving a message for a given user (even if it was already being forwarded by your provider)? It would route it back to your provider. There is no way to route messages based on who sends them, only on their destination; and the destination would be the same when the message is coming from Exchange itself, or when is coming from outside: if your wish could come true, you'd be stuck in a mail loop.

There are many things that need to happen here.

Set up your MX record
You need to create a DNS record of type MX that points to 'mail.foo.com'. This will tell incoming mailers that you receive mail destined for @foo.com at mail.foo.com.

Set up accepted domains
In Exchange Console, go to Organization Config -> Hub Transport -> Accepted Domains tab. Make sure that 'foo.com' is in this list, and set to default.

Set up email address policy
On the E-mail Addresses tab for Hub Transport, right click on Default Policy and go to Edit. Following this wizard will let you set up what email addresses Exchange assigns to users by default. This is where the choice of firstname.lastname@foo.com vs accountname@foo.com gets made.

Set up POP3 address
Create an A record in your DNS that points pop.foo.com to your lone IP address.

Set up POP3 access
Poke a hole in your firewall to forward tcp/110 to the server running the Client Access role. Back in Exchange Console, go to Server Configuration -> Your server -> POP3 and IMAP4 tab, select POP3 and click Properties. The defaults are probably OK, but check 'em. We don't use this service so I can't advise.

Set up incoming SMTP
DNS is already set so mail.foo.com is pointed at your lone IP address (that's the MX record in step 1). Poke a hole in your firewall to forward tcp/25 to the server running the Edge role (or your spam appliance, if you have one). If you don't have a server in this role, forward it to your Hub Transport server. If you have to use a HT server, you'll need to tell Exchange that it's OK to receive anonymous mail on TCP/25 on that server. To do that open Exchange Console, go to Server Configuration -> Hub Transport -> Your server. Double click on the Default policy. Ensure it is listening on TCP/25, and allows connections from anywhere (these are the defaults). On the Permission Groups tab, make sure the "Anonymous Users" box is checked.

Set up outbound SMTP
Create a DNS record for smtp.foo.com pointing to your lone IP address. Poke a hole in your firewall to forward tcp/587 to the server running the Hub Transport role. Go to Server Configuration -> Hub Transport -> Your server. Double click on the Client policy. Ensure it is listening on TCP/587 and allows connections from anywhere (again, these are defaults). On the Permission Groups tab, only Exchange Users should be checked. On the Authentication tab, ensure TLS is turned on. This allows your users to use smtp.foo.com as their mailer, so long as they're logged in.

Set up TLS access
This is a tricky thing to do. If you want your users to authenticate securely over the internet (and I bet you do) you'll need to configure a SSL certificate for use by this service. It will make your life a world easier if you get it from one of the major SSL vendors as client applications (including phones) won't complain about invalid certificates. And not all email applications allow importing new certificate authorities. These are called Unified Communication Certificates, and they're more expensive than the standard web-server SSL certs. But they're made for Exchange. You'll need to ensure that mail.foo.com and smtp.foo.com, and maybe webmail.foo.com if you decide to go the OWA route, are on the certificate.

That should provide enough hints for where to go from here to at least get you farther down the road. Good luck.