森本 裕桂ご提案ありがとうございます。残念ながら、私の環境では問題が解決しませんでした。状況が少し異なるようです。
お調べしたところ、絵文字の検索機能は、米国英語の言語パックに含まれる「基本的な入力機能」がインストールされている場合にのみ利用できるようです。
実際に、キーボード言語を「英語（米国）」に切り替えると絵文字検索は正常に機能しますが、それでは日本語のスペルチェックなどが利用できず不便です。普段使用している言語（日本語など）に戻すと、検索機能は再び使えなくなります（マウスクリックでの絵文字選択は可能です）。
ご提示いただいた手順についても、私の環境では「Microsoft Emoji」という入力メソッドの項目自体が存在せず、オプションを開くことができませんでした。
OSは会社のIT部門に管理されているWindows 10 Enterprise (v22H2 build 19045.3324) です。どうやら言語パックの機能制限が原因のようです。