Heres the scoop.....
There are 3 different XP Home types:
1. XP Home OEM
2. XP Home Retail (Upgrade)
3. XP Home Retail (Full)
Now, if your computer has the product key on the side of the case as you say, it is with no doubt a Home OEM. Any original Microsoft XP Home OEM disk will work regardless of Service Pack.
As mentioned above, manufacturers do not use this key during their installation. It is just there for licensing reasons. They either provide you with a disk to reinstall that has a product key built in and no activation, or no disk and give you a recovery partition on the hard drive.
In order to install any way other than the manufacturers setup, you need the correct Microsoft disk. Downloading from the net can be a nightmare as you will never truely know what disk you downloaded.
Find someone that has a disk and copy it.
Only in very very rare cases, you can enter the product key and use the correct disk, and it will not accept. Only computers I've seen this with is certain HP Pavilion laptops. Microsoft is aware of this problem and only solution they give is using the HP Recovery which does not ask for the key. (I think HP was printing bootleg product keys

)
Good luck.