Exchange 2007 Clients Dropped

We have an Exchange 2007 server and for some reason, the server will “drop” a user. The user will get an error saying something like Exchange server is not available and the server must be shut down and restarted before the user can log back into the Exchange server and get their email. We’re using Outlook 2003 for the client. We have applied all patches to the server but this did not cure the problem. There is no set pattern or user. We tried deleting their profile and recreating it but that still did not work. Only rebooting the server will allow the dropped user to log back in. Any ideas on what is happening ? Thank you.