Unable to Reinstall of Geniune XPPro

We had to purchase from Windows Genuine Advantage Kit for Windows XP Pro
Order Date: July 4, 2006

While this solved our problem with the Genuine issue we have since lost the hard drive in total… So, just start over…right? Nope!

The key that came with the SPECIAL COLORED CD, will not work, we keep getting the INVALID KEY..
ENTER WRONG RIGHT? Nope! 6 of us have entered it exactly off of the MS Tag and even took a photo of it and printed it out 4 x 6 and it is being entered correctly… Any ideas?