I've tried Everything I know of!

I just can't seem to figure this one out, and I consider myself pretty computer savvy. I checked my email and saw that my little brother sent me a suspicious email with a single link. I asked him about it, and he swears on his life he didn't send it. Well I thought his email was simply hacked, so I told him to change the password.
Now, his Windows XP computer has been infected. The viruses I've gotten the pleasure of running into are named:
- Worm.Win32.netsky
- TrojanDownloader: Win32/Fakeinit
- Trojan Spm/lx
I don't know if they're directly related or not, I just know that whatever I do, they won't rid themselves from the computer.
Here are the problems:
- Task Manager is unaccessible. Start > Run > taskmgr does not work, a pop up appears that reads "Application cannot be executed. The file is infected. Please activate your antivirus software".
- Registry Editing is also unaccessible. Start > Run > regedit gives off the same pop up as trying to run taskmgr.
- Wallpaper is changed so that it reads "YOUR SYSTEM IS INFECTED! System has been stopped due to a serious malfunction. Spyware activity has been detected. It is recommeded to use spyware removal tool to prevent data loss. Do not use th computer before all spyware removed." Yeah, it's spelled wrong.
- On the task bar, a pop up appears from the system tray that states I have spyware that needs to be removed (I know it is the virus's pop up because the icon is not from Windows)
- A lot of programs cannot be opened/accessed because of the same pop up box that appears just like the one when I'm trying to open taskmgr.
- In Firefox (I haven't tested in IE), when opening a link in a new tab, or when I do a Google search from the search bar installed in Firefox, the page immediately redirects to a malicious site or a phishing/spam page.
- Upon startup, a box pops up saying I have worm.win32.netsky:

Spyware Alert!
Security Warning!
Worm.win32.Netsky detected on your machine.
The virus is destributed via the internet through e-mail and Active-x objects.
the worm has its own SMTP engine which means it gathers e-mails from your local compter and re-distributes itself.
In worst cases this worm can allow attachers to access your computer, stealing passwords and personal data.
Viruses can damage your confidential data and work on your computer.
Continue working in unprotected mode is very dangerous.

Type: Virus
System affected: Windows, 2000, NT, ME, XP, VISTA, 7
Security risk(0-5): 5
Recomendations: It is necessary to perform a full system scan.​

- Once in a while, I'll get a pop up that reads "Attention! System detected a potential hazard (TrojanSPM/LX) on your computer that may infect executable files. You private information and PC safety is at risk. To get rid of unwanted spyware and keep your computer safe you need update your current security software. Click OK to download official intrusion detection system (IDS software)"

I've tried:
- Doing a full system scan with Mcafee, my main AntiVirus program (found nothing)
- Full system scan with Windows Malicious Software Removal Tool (got nada)
- Running ComboFix (it found and deleted some stuff that I'm not sure were related to the virus, problem still persists)
- Manually removing/fixing the registry keys that one of the virus changed (with help from a Microsoft page), but they change back upon reboot. Now, regedit cannot even be accessed.
Now here's the tricky part.
- I ran MalwareBytes (it removed a virus from the system a couple years ago when Norton couldn't) and it found 7 objected infected in the QuickScan and Full Scan (I ran both), and I had them removed immediately. However, when restarted, the virus(es) still remain. I run the QuickScan again, it finds the infected objects, I remove them successfully (or so it says), but they reappear.
- Windows Defender starts automatically when Windows does. At start up, I get an alert from WD that finds the TrojanDownloader:Win32/Fakeinit. I click "Remove All", and it "successfully" removes it, but all the symptoms are still there, and the next time I start up the computer, I get the alert again.
- SmitfraudFix is downloaded onto the computer but cannot be ran. I get the "Application cannot be executed" pop up.

I need to resolve this issue ASAP as I'm afraid of using my laptop, and both of us are behind the same router/network. I don't want anymore things to download and I don't wanna pay for anything because if I can't fix this problem, I'd rather just purchase a new system. For now, I've disconnected the infected PC from the modem and router and separated it from the rest of the other computers.
I can't post a HijackThis or a ComboFix log, because the programs won't load, but tell me whatever you need to know and I'll try my best to post it in a reply. Sorry the post is long, I just needed to make sure I was thorough and clear about the problem.

I've already followed the instructions in the RUN ME post!
Thanks in advance for any help!