O Explorer (Shell) não aparece

Alguém aqui está tendo problemas com o Explorer (não é o Internet Explorer) depois do windows update?
Pela última vez que pude acessar o log do sistema ele acusava erro no arquivo "verclsid.exe" dizendo que ele não poderia ser iniciado devido a um erro "desconhecido" e o event ID dele é 1000, ao fazer o logon apenas aparece o fundo do desktop e só consigo utilizar o gerenciador de tarefas para tentar executar algo, como estou fazendo com o firefox agora.

Procurei na internet por "verclsid.exe" no google e encontrei vários posts relacionados com este problema até que cheguei neste link da Microsoft:
http://support.microsoft.com/kb/918165/pt-br

Graças ao gerenciador semelhante ao explorer chamado A43 consigo acessar os drivers do meu computador, no entanto não consigo executar o regedit pois ele nem inicia, o visualizador de enventos também, MMC, Internet Explorer nada funciona e por isso não consigo fazer nada que diz o artigo.

Não é uma praga virtual (vírus, worms etc) pois o defeito ocorreu em 3 computadores diferentes recém formatados fora da rede e estes computadores estão detrás de 2 firewall's (roteador siems, linux iptables). A única coisa feita neles foi instalar o sistema operacional, drivers do chipset e executar o windows update. Os dois Windows XP e um Windows 2003 STD são originais.

Tentei chamar o suporte da Microsoft via telefone ou email mas nada foi resolvido, apenas perdi 4 horas do meu tempo ouvindo o "faz isso, faz aquilo" para ouvir que não sabem do que se trata.

Ainda bem que a cada etapa eu faço uma imagem do hdd e consigo restaurar o windows para antes do windows update, porém basta fazer o WU para o problema aparecer, enquanto eu não fizer o WU o sistema funciona sem problemas.

Alguém mais está tendo problemas?