Os arquivos, por acaso, são arquivos de mídia? Um motivo para o atraso pode ser porque o Windows está ocupado criando miniaturas.
Outro motivo pode ser porque você está excluindo arquivos de uma pasta que contém muitos arquivos.
Caso haja algum software causando o problema, você pode tentar inicializar no modo de segurança e verificar se ainda sente um longo atraso ao excluir arquivos semelhantes.
EDITAR : Muitas outras sugestões no TechNet .