Posso pensar em duas soluções (que você pode não gostar):
- Use outro navegador que não seja o Edge ou não use o Bing.
- Não use uma conta da Microsoft, que é onde seus dados são armazenados.
Veja o artigo Como reverter sua conta do Windows 10 para um local .
Enquanto você estiver interessado, também poderá desativar a maior ameaça a seu privacidade: Cortana (Veja este artigo ). O ponto 2 acima também bloqueará Cortana.
Como outra observação, os aplicativos de terceiros estão sempre seguros: Se você não usa os aplicativos do Windows 10 para navegação, pesquisa e e-mail, nenhum histórico é mantido.