Go ahead and try to download the Avira Rescue CD and create the CD and run the scan. If it does not work, it is not a loss. As to how you got infected in the first place, you could have been infected before you installed the security software, you might have installed a toolbar that was not friendly but was actually malware, or you could have installed the first piece of malware thinking you were installing something else. All the protection in the world is no good, if you allow the program (in this case malware) to be installed. It could have come in on an e-mail, or thru an infected CD or thumbdrive.
As for the reinstalling of windows, it is easy. As for personal documents, first we back them up so that you can restore them after reinstalling windows. As for passwords and the like, there are ways of getting those. As for a hidden file way in there that is infected, there is very little that can survive my method of reinstalling windows. If you have something that does, then you would need to replace your harddrive anyway.
As for the problem right now, I think the biggest problem is Windows is corrupted. The disk I want you to create with nlite might possibly be able to fix that problem. We can try using just the windows XP install CD that you have, but then you would have a boatload of Windows updates to do. If you do nothing now, it will get to the point where you will loose all your personal data and windows will be unusable, and you would be back to the point of reinstalling windows, but your personal data will be gone.
For now, the next best step is Avira.