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.
Seems to have been broken again or else the fix was not universal. Search All Mailboxes for non-Conversation views has not worked for me in months, if not over a year. Currently on Version 2201 Build 16.0.14827.20158) 64-bit (O365 version). I have a mix of Exchange, IMAP, and POP3 accounts, which may or may not be relevant to this functionality working as expected.