It depends on the way windows has been activated in the beginning I guess (but for sure someone more expert than me in licensing would explain better).
I don't think you can re-activate a Windows which had previously been activated by tampering the activation files (letting the PC believe it was an OEM copy from, say, Lenovo) just entering the "retail" key you obtain from a reseller. (Un)
fortunately I've never had to try that method (my AA copy activated fine for 3 or 4 times online in the last year, on the same PC to which I changed a video card once and a HD drive then) so I can't be further helpful
Again, I'm by no means a licensing expert so take what I say with some doubt