Demorou várias tentativas, mas consegui que funcionasse -
Eu não tive sorte com a remoção e reinstalação do XP Mode. Tem o mesmo problema ao tentar executar o Windows Update. Navegar na web funcionou bem com a VM.
Então eu atualizei manualmente para o IE8, e depois de uma reinicialização da VM, não pude nem mesmo navegar. Eu pesquisei as Configurações de Conexão do IE, desmarcou a opção "Detectar Automaticamente as Configurações" na caixa de diálogo "Configurações de Lan", e tive a internet novamente, enquanto uso o Windows Update!
Pode até ter funcionado no IE6 original - vale um tiro se alguém tiver um problema semelhante.