Microsoftアカウントにサインインしての利用でしたら、ダッシュボードに保存あれているかもしれないです。
次のページの手順（少し古い時期のものかも？）に従って、Edgeの「設定」→「詳細設定を表示」→「Bingの検索履歴をクリア」から開いたページで、「検索履歴の管理」の「クラウドの保存されている検索履歴を管理」リンクから開いたページ※で「消去」できないですか？
（“閲覧履歴消して、検索履歴消さず”それが命取り）
https://forest.watch.impress.co.jp/docs/serial/win10tips/1087351.html

※このページの「履歴設定の変更」にある「検索履歴で最近検索されたキーワードを表示する」をオフにしておくと、保存していても出なくなるかも？知れないです。

投稿日時 - 2018-03-08 17:27:59