[exim] Unrouteable address but email address is valid

I've got an interesting one. I just need to send email from our
helpdesk server using php mailer. I did a basic internet site exim
config using dpkg-reconfigure exim4-config. Sending is working fine to
all domains except one. The one it does not work on is one of two mail
servers that's on our local network. It has no problem sending mail to
the other mail server that's also on our local network. Here's an
example from the log file:
2012-01-24 15:05:32 1Rpg44-0005KV-Ma <= www-data@helpdesk U=www-data
P=local S=27621
2012-01-24 15:05:32 1Rpg44-0005KV-Ma ** name@???: Unrouteable
address (I edited this entry)
2012-01-24 15:05:32 1Rpg44-0005KX-PI <= <> R=1Rpg44-0005KV-Ma
U=Debian-exim P=local S=28402
2012-01-24 15:05:32 1Rpg44-0005KV-Ma Completed

It's almost like this helpdesk server thinks that the domain in question
is a local domain.
From normal email clients we have no problem sending & receiving to
this mail server in question.

What gives?