Windows Messenger 5.0 Exchange login issue

I have the following scenario:

Two seperate networks which are connected via a IPSEC VPN tunnel between
the two firewalls for each of the networks, Network A and Network B. The
Exchange server acting as the IM virtual server is on Network A.

This VPN is setup to allow ALL traffic between the two networks. All
traffic is passing across the VPN without a problem.

The problem is occuring with Windows Messenger 5.0 on computers in Network
B. When they attempt to sign in to Exchange Server they receive the
following message:

The email address does not match the username and password of the person
logged into this computer. Make sure you provide the correct username,
password and domain for the email address.


The users on Network B are are logging on to the domain via the VPN without
any hitch. All authentication is taking place against the DCs in Network A
and users on Network B can access resources on Network A without problems.

Now the strange thing is if these users log onto their machines using the
Microsft VPN client (Log on using Dial-Up networking at the logon prompt)
to establish a VPN connection via that method they don't have this problem.
It is only occuring when they are utilizing the dedicated VPN between the
firewalls.

Any ideas?