Look at the manual. You must put the headset in "discoverable mode" before a PC or phone can find it. Usually it involves turning it off then pressing the ON button longer, until the LED flashes red and blue. Of course this varies from device to device - read the manual.
Correct... The Windows XP drivers don't support Headsets, only the Windows Vista drivers. I remember a couple of years ago some Belkin Bluetooth adapters wouldn't pair or recognise headsets because of some hardware/firmware problem. It could be this the problem?