SBS Exchange Issue

I have a client who is running Microsofts Small Business Server 4.5 and is running into an issue with Exchange.

Anytime the server has been running for any lenght of time and you need to add a user or you go to setup a users outlook client, when you do a check name or adding a new mailbox the server can’t save it or can’t verify.

I try to shut down the exchange services and the directory store seems to hang while trying to shut down(left it for 20 mins once). The only way to get things running again is to shut down and restart the server.

Please when replying this is Exchange on SBS not straight NT and Exchange.

Thanks