BleepingComputer.com: Had a backdoor.IRCBot infection, can't access search engines.

The computer was acting weird, so I ran the Malwarebytes program and it detected one infection. The log shows it as

Registry Values Detected: 1
HKCU\SOFTWARE\Microsoft\Windows\CurrentVersion\Run|Windows Update Server (Backdoor.IRCBot) -> Data: C:\Documents and Settings\(computer owners' name)\46052bbb-5685.exe

It was supposedly quarantined and deleted, but the effects are still being seen. I am unable to access Google and other popular search engines. For example, I could type CNN.com (or any other website) and I'd be taken there instantly. But if I try google.com it continually tries to load but never succeeds. I am able to bring up a command prompt and ping google.com successfully, so I believe that this infection altered my system in an attempt to prevent me from using various search engines. Does anybody have advice on how to fix this, and what I should do to ensure that the system is completely clean? Earlier Malwarebytes active protection detected a "potentially threatening" incoming request from an IP address that I didn't recognize, but I'm not sure what to think of it. I really don't know what the next step should be.

First consider this.
One or more of the identified infections is a backdoor trojan.

This allows hackers to remotely control your computer, steal critical system information and download and execute files.

I would counsel you to disconnect this PC from the Internet immediately. If you do any banking or other financial transactions on the PC or if it should contain any other sensitive information, please get to a known clean computer and change all passwords where applicable, and it would be wise to contact those same financial institutions to apprise them of your situation.

Though the trojan has been identified and can be killed, because of it's backdoor functionality, your PC is very likely compromised and there is no way to be sure your computer can ever again be trusted. Many experts in the security community believe that once infected with this type of trojan, the best course of action would be a reformat and reinstall of the OS. Please read these for more information:

How Do I Handle Possible Identify Theft, Internet Fraud and CC Fraud?
When Should I Format, How Should I Reinstall

We can still clean this machine but I can't guarantee that it will be 100% secure afterwards. Let me know what you decide to do.

This is a somewhat old computer which was purchased used, I don't have Windows XP discs and likely wouldn't be able to talk them into giving me a new license for free. If it was necessary to ditch this installation completely, would it be suitable to install a free operating system, like Linux Mint or something similar, and let Windows XP lie dormant? I suppose that's what I'd have to do if I didn't want to spend any money.

This isn't my computer, so I'll ask the owners what their preference is soon. Do you genuinely believe that it's a lost cause and that a clean slate is the only way to go? If we were theoretically going to do it the hard way, what does that entail? I'd appreciate if you could explain in some more detail, and I thank you very much for your help.

More so from a Security standpoint. If you wanted to do bamking om here and such ,I wouldn't trust it.
We can clean it though if you want to use itfor other things.