It sounds like your clients are running in offline mode? Check the "send/receive" settings on one of the client machines. Tools, Options, Mail Delivery
Also, if your server's HD is so full you can't defrag the edb you might be having a problem server side. Have you checked the event logs on the server? System and Application. Also reboot the server...(quick and worth a shot)
Sry I can't be more help, but I haven't run exchange on NT in years. (thank god)
Edit: Is there a new firewall? It may be blocking UDP packets sent to update mailbox new mail notification, and clicking on mailbox sends mail send/receive packets which may come on the only port the firewall is expecting to see and allow for client ops.
See here for more coherent
http://support.microsoft.com/default...b;en-us;264035