Outlookの検索機能はWindows OSの提供するファイル検索機能を使用しています。何らかの理由でWindowsの検索用インデックスが破損していたり、あるいはインデックスの収集が行われていないと、Outlookの検索機能も動作しなくなります。
Windowsの検索機能はコントロールパネルの「インデックスのオプション」から設定出来ます。
「インデックスを作成する対象」のリストから「Microsoft Outlook」を選択して「詳細設定」のボタンを押して下さい。ここで「再構築」ボタンを押すと、既存のインデックスデータを破棄して再作成を開始します。
もしインデックスを作成する対象のリストに「Microsoft Outlook」が表示されていないなら「変更」ボタンをクリックして下さい。「インデックスが作成された場所の変更」のリストにチェックを付けると、インデックスを作成する対象としてリストに表示されます。
インデックスデータの再構築には暫く時間がかかります。半日ほど電源を入れたままにして様子を見て下さい。次第にきちんと検索にひっかかるメールの数が増えていくはずです。