When you perform a cross-premises search in a mailbox in a Microsoft Exchange Server 2010 hybrid environment, the search operation fails intermittently.
This issue occurs because the mailbox encounters a storage transient exception.
To resolve this issue, install the following update rollup:
2746164 Description of Update Rollup 6 for Exchange Server 2010 Service Pack 2
Microsoft has confirmed that this is a problem in the Microsoft products that are listed in the "Applies to" section.