検索履歴を削除しても、他のデバイスやクラウドに保存されている履歴が再び同期されることが原因です。すべてのデバイスやアカウントで履歴を削除することが、この問題を解決します。