Isso pode ser um pouco óbvio demais, mas o artigo oficial do Suporte da Microsoft tem dois métodos possíveis para alterar a chave do produto. O primeiro é certamente aquele que você já tentou, mas há também um segundo método usando um VBScript.
Se você copiar e colar o VBScript fornecido no artigo da Microsoft link em um editor de texto como o bloco de notas, salve-o arquivo com uma extensão .vbs (use aspas ao redor do nome do arquivo se você achar que a extensão .txt é anexada automaticamente).
Em seguida, execute esse script com a nova chave do produto como um argumento, conforme mostrado nas instruções fornecidas abaixo do script. Obviamente, se você notou o salvou na raiz de sua unidade C: \, o comando exato que você precisará digitar na caixa de diálogo de execução incluirá o local onde você a salvou. Como alternativa, você pode executar isso no prompt de comando da mesma maneira.