Exchange 2010: Search-Mailbox fails with Event ID 3003

I was recently looking to perform a search of a mailbox containing keyword items, on performing this using the Search-Mailbox cmdlet, this would immediately fail with the following application error for the source MSExchange Mid-Tier Storage, with the ¬†Event ID 3003: Search ‘SearchStatus\e21eb91d-050a-4a5d-be1f-a10349672425’ has following error: An error occurred when searching *****. The message is … More Exchange 2010: Search-Mailbox fails with Event ID 3003