If you are certain that you have paid for Windows XP and the use of the product number, it is imperative that you locate the CD if you lost it since the product number can only be used twice (Assuming it is an OEM or Upgrade of either Home or Professional) and you will otherwise have to phone Microsoft to have your product reactived.
Also, if you are certain you did not loose the Windows XP CD (Which is rather difficult, considering the shiney-ness factor) you should use your receipt to demand a copy of Windows XP from the store you bought it from.. Assuming the code/name is actually on the receipt, however, I am certain that you know how to handle the customer-complaint section of this story..
But before you do either, be certain that Windows XP is not located on a recovery CD. It may not even be named Windows XP and you will not notice it is on the CD until you insert i in the CD/DVD-ROM drive.