Nuking um computador em caso de suspeita de infecção por malware é a opção que tomamos no meu local de trabalho (escola). É mais rápido do que tentar limpar o malware manualmente.
A legalidade do Windows é uma besta muito estranha, mas eu diria desde que a empresa esteja licenciada para a versão do Windows que está sendo implantada (ou seja, tem 20x computadores com adesivos OEM). deve ser ok, no entanto dizendo que eu não sou um advogado.
Se você estiver preocupado, pergunte a ele. Se ele não puder lhe dar uma resposta decente e direta, então é possível que seja uma versão esquiva do Windows e hora de pensar em se mudar. (Eu ficaria feliz em trabalhar em um lugar com software ilegal? Na verdade não. Eu ficaria feliz trabalhando como um administrador de sistema que é esperado para usar software pirateado? Não. Porque é a minha bunda na linha).