Why do I have to keep using the send/receive feature in Outlook 03'?

I have 3 users (all running XP & Office 03') complaining that they constantly have to hit F9 or "send/receive" to be able to send or receive messages. This all started about a month ago, but not all three at the same time. I have run extensive cleanings on the pc's, made sure that all updated have been done (Office & system). I tried the detect & repair tool. I checked to make sure that Office is not offline. I have also checked to make sure their individual mailboxes are not approaching their size limits...not sure what else to do. Should I delete, then setup their mail accounts again on their individual workstations? So far none of the users running Windows 2000 & Office 2000 or XP with Office 07' have been having any issues with Outlook.
I am running Microsoft Exchange 2000 on an NT server, 5.00.2195, Service Pack 4, Pentium 3, 1133MHZ, 1GB RAM, 160GB drive with 19GB's free space. I am allowed 16GB's for my database file & right now it's at about 14GB's. I have taking old users & archiving their mail accounts to different drive to create more space there as well.
Any & all responses are greatly appreciated.