try using the program Killdisk. This will permanently erase everything that has ever been written to the HD. Whenever I run into this problem, I run this on the HD and Presto, setup now recognizes the drive.
However, if this is a SATA drive, sometimes certain drivers must be loaded first. These drivers can be found at the manufacturer website. Once downloaded, you will have to use a floppy disk to load them (or usb flash drive if it is set up as bootable device). To load the drivers once downloaded and stored on bootable device, you will have to run winxp setup and press F6 when prompted at the bottom of the screen to load third party raid or scsi drivers. When you press F6, nothing different will happen. Setup files will continue to copy and setup will again try to look for your hard drive. When it does not find it, you will be prompted to look for drivers on your bootable device (the floppy/usb drive you loaded the drivers on).
Just note, after using killdisk, data recovery will not be possile for the partition you erased by using killdisk. What this means: Everytime your format a HD using Fdisk or windows setup, nothing is technicaly erased until that particular spot on the HD is written over, that is how data recovery businesses restore lost or erased data. Once you run killdisk, it re-writes over all data making it completely invisible to partition recovery programs. If you are not worried about any data on the disk, then this should be no concern for you, just some info.
If this does not help, I will be happy to walk you through the manual HD setup in winxp setup procedure, it is quite easy once you find what you need.
Hope this helped!