Este tópico do fórum é sobre um problema muito parecido com o seu, mesmo no Windows XP. O usuário achou o problema como relacionado a vírus. Em particular, eles descobriram que estava relacionado à seguinte chave de registro
HKEY_CURRENT_USER\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies\Explorer\NoRecycleFiles
Por favor, verifique se o valor está definido como 0 e faça uma varredura com um antivírus, possivelmente no modo de segurança.