私も同じ問題で長時間悩んでいましたが、別の方法で解決しましたので共有します。
私の場合は、問題が発生しているアカウントとは別の管理者アカウントでWindowsにサインインし、以下のフォルダを削除することで直りました。フォルダを削除後、元の自分のアカウントでサインインし直すと、検索機能が復活していました。
%USERPROFILE%\AppData\Local\Packages\Microsoft.Windows.Client.CBS_cw5n1h2txyewy
どうやらユーザープロファイルの一部が破損していたようです。他の方法で解決しない場合は、試す価値があると思います。