mail not visible

One of our subnets is using NAT configured at the router. Users get email from an Exchange 5.5 Server on another subnet. The problem we are seeing is in Outlook. Clients are using Outlook 97-2002. Some users get no notification of new mail (althoughit is configiured to do so) and are not seeing new mail in their Inbox although it has been delivered. Generally they have to do something like open a different folder and then return to the Inbox in order for the new mail to be visible. This subnetis the only one having this problem.
Any ideas?
Thanks