I updated to Office 2013 not long ago and when I searching for old items they do not appear, but instead at the bottom of the search result it displays:
Showing recent results...
More
First I though this was some setting with the indexing in Windows 8 but Outlook was selected as a source. Then I stumbled upon a support article “Only a subset of your Exchange mailbox items are synchronized in Outlook 2013” which solved my issue. The setting also applies to Calendar, Contacts, Tasks, Journal and Notes items.
By default with Outlook 2013 and using Cached Exchange Mode only the past 12 months are synchronized. Changing this to “All” fixed the issue and I can now search all my items offline and quickly.
The above support article lists the steps on how to change how much to cache locally.
