When searching for emails in Outlook 2013 using Instant Search the returned results may be limited. By default, 12 months of your email is available offline, but you can control how much mail is kept offline. In order to improve performance of the Instant Search feature in Outlook, by default the search results list is limited to the most recent 250 items that match your search query in Outlook 2013. Below the search results you will see Showing recent results… followed by More.
When clicking on the More tab the search query switches to using Exchange Search and no longer uses the local search. There is a 250 cap limit set on the Exchange Search side so the search results will be limited to 250 items even though there may be more items on the server related to the query. This cap is set at the Exchange side for performance reasons.
If you have an Online Archive mailbox attached to your Outlook 2013 profile the search queries are performed by the Exchange Server. Outlook doesn't create a local copy of the archive mailbox on a user's computer, even if it's configured to use Cached Exchange Mode. Users can access an archive mailbox in Online mode only. You can tell the mailbox is in Online mode by viewing the Status Bar at the bottom of Outlook.