The Elder Geek has an excellent set of instructions for doing a clean install of XP. You do not have to reformat your hard drive first. Formatting is included in the installation process and you can do it with your XP installation CD.
http://theeldergeek.com/clean_instal...windows_xp.htm