Assume that you perform a search on mailboxes on a Microsoft Exchange Server 2007 server. In this situation, the Microsoft Exchange Information Store service may stop responding. Additionally, you cannot access the mailboxes on the server, and messages delivery is delayed.
This issue occurs because of a deadlock between a search thread and a delivery thread in the Store.exe process.
To resolve this issue, install the following update rollup:
2608656 Description of Update Rollup 6 for Exchange Server 2007 Service Pack 3
Microsoft has confirmed that this is a problem in the Microsoft products that are listed in the "Applies to" section.