2019/06/26 追記
Officeが、Microsoft® Outlook® for Office 365 MSO (16.0.11727.20188) 32 ビット になって、
2019-06 x64 ベース システム用 Windows 10 Version 1809 の累積更新プログラム (KB4503327)
2019-06 x64 ベース システム用 Windows 10 Version 1809 セキュリティ更新プログラム (Adobe Flash Player 対応) (KB4503308)
を適用したら検索が機能するようになりました。レジストリPreventIndexingOutlook は 0 にしました。
本題はここから。
6月の10日ころから、Outlookで検索ができなくなりました。
キーワードを入力して検索してもまったくヒットせず、「結果はありません」と表示されます。
Windows 10 64bit（1809の最新）で、Officeは365 Businessです。
Outlookのバージョンは Microsoft Outlook for Office 365 MSO (16.0.11629.20238) 32 ビット です。
解決のためにやったこと。
・Windows Searchサービスの再起動
・Windows Searchのインデックスの再作成
・Officeのクイック修復
・Officeのオンライン修復
・Outlookデータファイルの修復（scanpst.exeの実行）
・ESETを使っているので「保護の停止」と「ファイアウォールの停止」をしても変化なし
・動くようにとお祈り
どれも効果なしでした。
試しに、Outlookをセーフモードで起動（Winキー＋Rで「outlook /safe」）して検索を試すとヒットします。（→セーフモードではインデックスを見に行かないで都度検索するようになるから）
いちおう、すべてのAdd-inを無効にしてOutlookを再起動したり、Windowsの再起動をしたりして通常起動を試しましたが、やはり検索できません。
イベントログには
プロトコル ハンドラー Mapi16 を読み込めませんでした。エラーの説明: (HRESULT : 0x80004005)。
なんていうメッセージが、検索を実行するたびにログされます。
というわけで、OutlookからWindows Searchのインデックスを参照するのをやめて、「都度検索」で動くようにしました。根本的な解決ではないし、表示に時間がかかりますが、検索ができないと話しにならないので、しばらくはこれで様子見です。（低スペックでHDDのパソコンの人にはおすすめしません）
その方法はというと、
Outlookを終了させた後、
regeditで、
\HKEY_LOCAL_MACHINE\SOFTWARE\Policies\Microsoft\Windows に
Windows Search というキーを作って、
そこに、DWORDで PreventIndexingOutlook を 1 で作成します。
自己責任で。
レジストリのバックアップは regedit の エクスポート で採っておきましょう。
ぐっどらっこ。