It wouldnt still be on if you started over with a clean format but you shouldnt need to do that. its a big job and you will create more problems than you solve if you arent confident in what you are doing mate.
Download and install Lavasofts Adaware
http://www.download.com/Ad-Aware-Ann...-10045910.html
- restart your pc when prompted.
Just click to close the box when it asks about registering - this is 100% definitely free ( the other one is too !
)
Download all updates for it then do a complete scan - it should remove many browser hijacks.
Also, if you click ( on XP ) Start/Control panel/Add Remove programs. Check the list for software that you dont use. if you are able to, type the name of any software that you are unsure of into google and read what it is. If its iffy - someone will of already done a thread somewhere on it. Just remove anything that you dont use.
Once thats done, do a defrag ( start/all programs/accessories/system tools/disk defragmenter )
Once you have done all of the above your computer should run much smoother - it will take some time to do all this so be patient and bear with it - its a world quicker than a complete reinstall and downloading all your drivers and MS updates again !
Cheers