No need at all to use another OS (like Linux) to format the hard disk. It's a task very well done by the Windows XP setup program. Moreover, that reinstalls Windows immediately after formatting, and that's probably what you want. Maybe you even have a manufacturer made restore CD, that includes all those drivers you need to run the PC again.
A few remarks, however:
- Most of the time a full hard disk is caused by system restore data (takes a few clicks to clear), old temporary files (that can be cleared with disc cleanup or free ccleaner), old programs you never use anymore, and can be removed) and just your own old stuff (maybe you don't want to lose that, as happens when formatting). Some careful cleaning can make the system go on for quite a long time probably.
- It seemed you used the wrong way to reload Windows. Tell more on how you did it, and what options you chose.
- Add/remove only removes programs. Generally, they don't use that much space.
- Maybe tell some specifics, like size of disk and free space available.