Windows Product Key Update Tool Instructions: http://www.microsoft.com/genuine/selfhelp/pkuinstructions.aspx
Please note that the Windows Product Key Update Tool can only be used if you have the same version of Windows XP as the installed non-genuine version. For example, if there is a non-genuine version of Windows XP Professional installed on your computer, you can only use the Windows Product Key Update Tool if you have a valid Product Key for Windows XP Professional (Full Version...not an Upgrade Version).
If you have a valid Product Key for Windows XP Home Edition, then the Windows Product Key Update Tool is not going to be of any use to you and a "clean install" of Windows XP Home Edition would be required.
How to perform a clean install of Windows XP: http://www.michaelstevenstech.com/cleanxpinstall.html
Performing an HP System Recovery in Windows XP: http://h10025.www1.hp.com/ewfrf/wc/document?cc=us&docname=bph07145