This is fixed in Monthly Channel Version 1712 (Build 8827.2179). To get the latest update immediately, open Outlook and choose File > Office Account > Update Options > Update Now.
Instant Search is not working for some users, specifically, the All Mailbox search returns no results. This only affects users who don’t use the conversation view. If you use the conversation view (Show as Conversation), All Mailbox search works "as expected".
The Current Folder and Current Mailbox search scopes work, regardless of the Show as Conversations setting.
To group by conversations, switch to the View tab and tick Show as Conversations.
With Show as Conversations enabled, the All Mailbox search scope works.
