Spybot will not run on infected computer

[Noobster]

I am trying to repair a badly infected laptop but am having little luck. The laptop is a friends and they never had working virus scanner installed or received windows updates. I have some experience with repairing computers but this is over my head. At this point I would format the hard drive and re-install windows, but the laptop's owner doesn't have their windows CD and the product key was on a sticker at the bottom of the laptop which has since been scrapped off.

The symptoms of the infected laptop are as follows:

Extremely slow and un-reliable windows start up (>5 minutes, often locks up before finished).
High CPU usage while idling.
Homepage of IE 6 is re-directed to a psuedo anti-spyware websites (PCPrivacyCleaner, VirusRemover2008, etc) which then causes IE 6 to lock up.
Web searches on Firefox are re-directed.

To remedy this I recently installed McAfee from AOL and Spybot. McAfee detected several items and removed some but could not removal all of the items. Now it will no longer update and claims it needs to be "fixed." I tried to install Spybot but unfortunately it will not run. In Spybot's install directory I don't even see SpybotSD.exe. I also checked the internet protocol (TCP/IP) properties to make sure addresses are obtained automatically and flushed the DNS cache hoping to solve the webpage re-directions but this did nothing. I read on the FAQ section about Spybot that the computer may be infected with CoolWWWSearch.SmartKiller and downloaded the removal tool. The removal tool did not detect either version 1 or 2.

At this point I have no idea what to do and any help would be greatly appreciated. If anyone is looking for a challenge, I have one for you.

[Noobster]

Update:

I've been reading through some of the forum and found that a lot of people have been downloading hijackthis to create a log of potential problems. I have downloaded hijackthis from another computer and moved it to the infected laptop with a flash drive. Unfortunately, hijackthis will not run. When I try to run the install program nothing happens. The install does not begin and there are not any error messages either.

Using msconfig I tried to prevent all unessential programs from loading when windows loads. One item I found questionable was called ‘bxoepyqn’ which windows said used the following command: rundll32.exe “C:\WINDOWS\system32\bxoepyqn.dll’’,b (this is all typed correctly).

I went into the folder C:\WINDOWS\system32 and found rundll32. Oddly enough, when I right clicked on the file I had the option of scanning with Spybot so I did. It scanned only this file and detected Smitfraud-C. I don’t have the option of performing any type of removal or repair however.

Also, I have put Microsoft’s malicious software removal tool on the laptop but windows will not execute the file, just like with Spybot and hijackthis.