Windows XP and Logon Credentials Have Failed

I am currently working with a few people who are using a
Dial Up or VPN Connection (PPTP and IPSec) into an
Enterprise Company with either Windows XP Home or Pro. The
problem is that once they are connected they are
attempting to connect to and Exchange 2000 Server and
receiving the error "Logon Credentials Have Failed"
or "Your MS Exchange Server is unavailable." Outlook 2000
or XP will continously prompt for Login Credentials, even
when not selected.

They can ping the servers by host name and IP Address,
tried to create a new profile using both, receive the same
symptoms. I have followed these MS Q Articles

http://support.microsoft.com/default.aspx?scid=kb;EN-
US;163576
http://support.microsoft.com/default.aspx?scid=kb;en-
us;268575
http://support.microsoft.com/default.aspx?scid=kb;en-
us;272290
http://support.microsoft.com/default.aspx?scid=kb;en-
us;307926

None of these solutions work. The strange thing is that a
customer can use Outlook 2K or Outlook XP to access their
local Internet Email but not Corporate. The last resort
would be to uninstall and reinstall TCP\IP, ususally this
works, but I don't understand why we would have to do this.

Any thoughts??