My wifes laptop has a ton of issue due to her last companys software. It is a Fujitsu bought new from Frys. It cam with XP installed but did not come with XP disk.
You can use AutoRecovery which doesnt need an Xp cd. If that doesnt work, you would have to go out and buy a copy of Xp. But definitly try the Recovery thing first.