Okay... have whoever runs that VPN appliance check to see if UDP packets are
being routed and/or blocked. Here is a Microsoft KB article that might
explain better why Outlook doesn't refresh itself when new mail items arrive
(e.g. they have to switch folders to see new items).
http://support.microsoft.com/default.aspx?scid=kb;en-us;264035&sd=RMVP
In your subject line it cut off the version of Outlook, but later versions
of Outlook can be configured to poll the exchange server rather than rely on
that UDP packet. (This applies to Outlook 2000 SP3, Outlook 2002 SP2/3, or
Outlook 2003) If you need help searching support.microsoft.com for the
relevant article, don't hesitate to ask for help. (magic keyword for the
search is "Force Polling" or "ForcePolling")