I have a network with 500 local PC's and 3500 total users supporting local
and remote access.  Two back-end Exchange 2003 servers, two front-end.  
Servers were recently upgraded to Exchange 2003.

Recently, some computers are unable to use Outlook 2003 to access Exchange.  
I've tried recreating the account information, pointing to different Exchange
servers (with appropriate accounts) and logged in with accounts with various
permissions.  All clients are running Windows XP Pro with SP2 and are
regularly updated with WSUS.  All clients are running Outlook 2003, also with
SP2.  I verified from two clients, one that works and one that doesn't, that
both have all the updates.  Access fails for all users, regarless of
permissions on the clients.  I've tried with lowest user and with an Admin
account.

Most of the clients that are failing are behind a Windows RRAS NAT from the
Exchange box, but even that is not consistant as a some still work fine.

From a client that is not working, I've tried changing Outlook login from
Kerberos to NTLM, I've killed all Outlook profiles, everything short of
reinstalling Outlook.

Web access works fine on all accounts.

Any ideas would be appreciated.