First, there is no such thing as a "any legal product key." There is a legal key to a single install of Xp, both Home Edition and Pro versions.
The sticker on the bottom of your computer is the license key to the Operating System that was installed at the time it was built.
If you have a Retail version of XP Pro, the OEM key on the bottom of your computer will not allow it's installation.
You need to purchase a new OEM copy of Xp Pro or Retail.
You may be able to locate a set of rescue disk for your particular computer make and model online as there are a few companies that still have them for sale.