This led me to check Microsoft’s Answers site. Here I found . This, in turn, led to another helpful . The postings on these pages contained several potential solutions. While no one solution worked for everyone, there was agreement as to the most likely road to success. It’s a road that may surprise you: Outlook depends on OS X’s Spotlight database for its searches. Therefore, anything that causes problems between Spotlight and Outlook may prevent Outlook’s searches from succeeding.

The top recommended solution is to re-index the relevant Outlook data in Spotlight. To do this:

1. Open System Preferences and select the Spotlight pane.

2. Click the Privacy tab.

3. From the Finder, go to your Home directory -> Documents -> Microsoft User Data folder. Locate a subfolder named Office 2011 Identities.