What does the disk access on the server look like when the users log into the mailbox? Memory usage?
The only thing I can really think of here is it is getting hung up on slow disk access, not sure if reindexing will help or not but it's the only thing I can really think of as well... |