Estou assumindo que, mesmo depois de excluir os arquivos, o Windows ainda mantém um cache deles, portanto, mostrado nos resultados da pesquisa, pois a maioria dos arquivos é indexada pelo Windows.
O que você pode fazer aqui é tentar limpar o cache:
Veja como você faz isso:
clique com o botão direito no disco rígido - > propriedades - > Limpeza de disco - > verifique a lixeira, arquivos temporários e miniaturas e clique em ok.
Acredito que isso resolverá seu problema.
Espero que tenha ajudado. :)