Event ID 9877 with error code "0x80041606" when you use Outlook in online mode to search for a keyword in Exchange Server 2010

KB Article: https://support.microsoft.com/kb/2616127

INTRODUCTION

Consider the following
scenario. By default, Exchange Search is enabled for a mailbox database in a Microsoft Exchange Server 2010 environment. You use Microsoft Outlook in online mode to search a mailbox for a keyword or phrase that contains a single letter or a single digit. In this scenario, you receive the following error message even though there are matches for the keyword in the mailbox:

No matches found for "keyword".

Additionally, the following event is logged in the Application log:

Log Name: Application

Source: MSExchangeIS Mailbox Store

Date: Date

Event ID: 9877

Task Category: Content Indexing

Level: Error

Keywords: Classic

User: N/A

Computer: Computer

Description:

Content Indexing function 'CISearch::EcGetRowsetAndAccessor' received an unusual and unexpected error code from MSSearch.

Mailbox Database: Mailbox Database

Error Code: 0x80041606

NOTE:
0x80041606 = QUERY_E_TOOCOMPLEX