Lo mejor que puedes hacer es llamar a Microsoft, ellos te daran una solucion en no mas de 2 minutos.... te lo aseguro.
Eso si, tienes que tener MUY CLARO que as exo para que te ocurra esto.
Es decir, as cambiado mucho hardware??, o por el contrario, as comedito el GRAVE ERROR de dejarle tu key a un amigo???, de ser asi, lo tienes muy jodido (aunque se de casos en este foro de que a colado, y por los compañeros que lo dijeron... les creo la verdad).
Si as cambiado mucho hard, no hay ningun problema, ellos te daran una nueva, ese tema taba mal pensado desde el principio y lo saben xD.
De todas formas si llamas, dile lo del hard, que has cambiado todo menos la placa madre y veras como te dan una nueva (si la anterior es correcta

)
Un saludo.
PD:Se estan dando muchos casos de estos...

, fallo en el sistema interno de reconocimiento??? un poco raro esto.