If you found out your Microsoft products to be ungenuine, you will have to deal with the result. I think fixing it will be a great option because ungenuine operating system and programs cannot get adequate security patches and enhancements.

By fixing I mean becoming genuine Windows legally.

Microsoft had anticipated the need of legalizing Windows on the fly, so that they released a very useful little utility named Key Update Tool, which can be found here:

http://download.microsoft.com/download/8/3/7/83712767-395c-4327-8e87-38be7b0cf75f/KeyUpdateTool_enu.exe

Snap1

Proceed ahead, and after the program finish checking the system files, it will prompt you to enter new product keys.

Enter the genuine ones you purchased legally, and it will automatically change it to make your OS genuine.

Snap2

If you had Internet access, this key update tool will try to automatically activate the product key for you during system startup, which might cost several seconds.

After you activated your Windows, everything will be alright.

One thing to keep in mind that this key update tool can only be used in Windows XP. In later OSes like Windows Vista, changing product keys can be very easy, thus eliminating the need for Microsoft to release any discrete program for this.