[Exim] Problem with Microsoft Exchange

exim 3.12, Debian distribution. Simple rewriting rule of the form

*@domain.com $1@??? T

is OK when first sent to a sendmail relay and thence to Microsoft
Exchange.

However,

#@domain.com $1@??? T

where micro.soft.com is the fully qualified name of the Exchange server
gets me a variety of "unknown user" messages from Exchange. Running exim
in test mode indicates that the address rewriting seems to be proceeding
as expected (the envelope TO address is properly rewritten). I smell a 7/8
bit problem here, but I really have nothing solid to work with.

Can anyone offer suggestions on circumventing or fixing the problem (no,
getting rid of Microsoft Exchange is __not__ an option <g>).

Copy to private mail would be appreciated if it isn't too much trouble (I
get enough mail to have put exim-users on digest).

Thanks in advance,

Murray Gross
mgross@???