No entanto, num dos PC's houve um erro no Windows update que me roubou horas de pesquisas. Assim de cabeça, se não me engano, era o 80246002
E tudo o que aparecia no Google eram posts de há menos de 12h e ninguém apresentava uma solução. Se alguém aparecer por aqui com esse problema, ficam já a saber que a solução (temporária acho eu) é alterar o servidor DNS para 8.8.8.8 e 8.8.4.4 no ipv6 e ipv4 (valores de cabeça mas acho que são estes. São os do Google)
Fiz isso e resultou e as actualizações já foram encontradas e instaladas.