Do you have a XP cd? if so you may be able to do a repair install if the cd is the same Service pack as what you have on the computer. If say the cd is SP2 and you have SP3 installed, its best if you uninstall SP3 then do a repair install.
Otherwise, for a totally clean install, make sure the computer is set to boot from cd first then the HD (check in bios).
Insert Win XP CD, reboot computer and install.
If its a newer computer, there may be a partition on the hard drive to do this.
Google your computer manufacture's website for your model and to see if you have a repair partition.
You may also have good luck with posting in the malware removal forum to remove virus/malware. Most of the time its not a huge issue to get rid of malware.

 

This is a good guide to reinstalling XP . . you might want to print it for reference during the install.

XP Clean Install