I have such trouble with rewriting mail headers.
In exim.conf:
...
# REWRITE CONFIGURATION
*@localdomain $1@externaldomain FfRs
#
...
When I send message from localhost(server) all ok
When message sent from MS Outlook Express from other PC message received with
user@localdomain address in it's header.