Have you had the "pleasure" of calling them for this issue?If you change enough hardware to trigger a need to reactivate, you make a phone call to Microsoft and explain the situation - a phone call, that's it. It even says as much in the Windows 10 FAQ.
I have and here's how it went down...I called them up, the first tech tried to change the product ID manually, transferred to a higher level tech, that tech tried to have me use a new key, transferred to a higher level tech. That tech actually RDP'ed into my computer, tried all the things I'd already done, all the things the previous tech had done, and then concluded with telling me to go to the forums...and there was nothing more she could do.
My desktop remains unactivated. I'll go through starting from 8.1 and reinstalling 10 after I replace the motherboard this weekend. I'm keeping my fingers crossed it's as easy as that but so far it's not been anything even remotely close to what people on here seem to be parroting from the FAQ without the direct experience I've had.