The Exchange Information Store service stops responding when you perform a search operation on an Exchange Server 2007 mailbox in Outlook

In a Microsoft Exchange Server 2007 environment, the Microsoft Exchange Information Store service (Store.exe) stops responding when a client performs a search operation in Microsoft Office Outlook. At the same time, all mail flow to the server stalls and no users can connect to the server. To recover from this issue, you have to perform one of the following actions:

1. Restart the Microsoft Exchange Information Store service.
2. Failover to another Exchange server node.
3. Restart the server.
   
   

The issue occurs because of a deadlock situation between both threads in the Store.exe process. One thread performs sorting operations and the other thread performs notification operations.

To resolve this issue, install the following update rollup:

Microsoft has confirmed that this is a problem in the Microsoft products that are listed in the "Applies to" section.