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.