This also happened to me when Installing Service Pack 1. For me, Windows XP had been pre-installed by the OEM, and the Windows XP license number sticker was attached to the outside of my computer's case, and I had the original (pre-SP1) installation CD. I had not registered with Microsoft, but had Activated my Windows XP months before installing SP1. In my situation, I called the Microsoft support number which was displayed on the activation screen, answered all the automated questions, repeated the answers when an actual person asked me the same questions, explained the situation, gave Microsoft the name of the computer manufacturer from which I purchased the PC, and they simply issued me a replacement product key number which worked just fine.