O histórico "Run ..." pode ser encontrado no Registro em:
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\RunMRU
Então, execute 'regedit', navegue até a ramificação acima e selecione e exclua as chaves apropriadas.
As entradas do histórico da caixa Pesquisar no Windows Explorer (e as entradas na lista 'Documentos recentes' em muitos outros programas, como o MS Office) podem ser removidas seletivamente simplesmente destacando-as e pressionando 'Excluir'.