Outlook for Mac wasn’t finding all my emails when I searched.

The solution was to reindex spotlight.

As root:

mdutil -E /