If you purchased a legit copy, you should have all the appropriate documentation. Call up Microsoft and explain your problem.
What ticks me off is that I have 2 legit copies of WinXP... one for my desktop and one for my laptop (dedicated licenses). Each has a max install of 5 times and everytime I do a major upgrade, I have to reinstall. I HATE having to phone up Microsoft to get a confirmation code (or whatever) just to get the software that I purchased running.
grrrr.... bollux to Microcrap!