O problema foi a Validação de Arquivos do Office, que foi enviada pelo Windows Update esta semana. Consegui apresentar esse problema em uma rede separada. A remoção da Validação de Arquivo do Office resolve o problema.
Este patch foi apenas para o Office 2003 e 2007, então 2010 não foi afetado.
Atualização do MS KB: link