Unable to reinstall Windows XP

My computer has been affected by a number of problems lately that I believe to be related to a virus.  Symptoms include:

-All pictures or chat features (gmail chat, for instance) not loading in Internet Explorer. 

-Google or Yahoo links redirect me to the wrong web pages.

-Norton and McAfee Virus protection software (purchased since being affected) get hung up in the installation processes and will not complete.

(I also notice that an instance of IExplorer.exe is constantly running in task manager even when I'm not running explorer.)

Because I have been unable to locate or remove the infecting virus, I have backed up all necessary files and decided to reformat my entire hard drive and start over as I have done in the past.  Recently I was able to do some sort of quick reformat without using any installation cd's.  The whole process was started by pressing F-something on startup and was very quick.  Unfortunately, I can't remember how I was prompted to do this at the time, but whatever it was, was super easy.

I do, however, have the Operating System / Windows XP reinstallation CD and decided to try that.  The problem is that it begins the process, and then restarts my computer... and gets hung up on a BLACK SCREEN with a cursor in the upper left corner.  I've left this screen up, just to make sure that it wouldn't require some time to load anything, and even after leaving it up all night, I found the same black screen in the morning.   I've tried it a number of times, and every single time, the same Black screen hangs up the reinstallation process.

I would love to rid my computer of these problems in any way possible.  Whether I'm able to find and delete the virus, be able to install my recently purchased McAffee Antivirus software (when the installation begins, it claims that I'm not connected to the internet and won't continue any further), or simply be able to start over and reformat the HD... I just want to get this fixed...

Anyone have any idea what might work?

Thanks,

Mark W