Connecting to Exchange 5.5 from home pro

Using Outlook 2002 from home running on winxp pro to connect to Exchange 5.5sp4 running on nt4 sp6a. All users are using cable to connect on their end and the Exchange server is on a T1. All users trying to connect to the exchange server over the internet through a firewall, gets the following informational message: “Outlook is retrieving data from the Microsoft Exchange Server . You can cancel the request or minimize this message to the Windows taskbar until Outlook closes the message automatically”. This happens often and the size of the mailbox does not seem to matter but while this is going on, no other work can be done and it may last up to a couple of minutes. Anyone seen this before or better yet have a fix?