Pressione Windows + R e cole o seguinte no campo Open
:
reg.exe ADD HKCU\Software\Microsoft\Windows\CurrentVersion\Explorer\AutoComplete /v AutoSuggest /t REG_SZ /d no /f
e clique em OK
Isso desativa o recurso de sugestão automática. Não tenho certeza se desativa o histórico em si. Você pode tentar desligá-lo, usar o Explorer por um tempo e ligá-lo novamente para verificar se você tem itens recentes no menu suspenso.