Repairing parental computer damage

[vsp]

My dad called me for some tech support recently, as his computer was running like a constipated wombat. Specs: Dell desktop, WinXP (upgraded from WinME), 800MHz, 128MB RAM, ~3.5GB free out of 10.

Problem 1: AOL 9 was indeed chugging tremendously on startup, hanging on "Step 4: Requesting network attention" for quite a while (a few minutes in some cases). AOL 7.0 (still installed) didn't have that problem. So far, so good, especially since I'm steering him towards dumping AOL and getting Verizon DSL soon. But...

Problem 2: I started running some common anti-malware apps. Ad-Aware 6 came up relatively clean (the usual assortment of Data Miner cookies, nothing else). Norton Antivirus was out of date, so I resubscribed him for a year's worth of definitions, and it found one virus: Downloader.Trojan, which had hijacked Windows Media Player. That got quarantined quickly, and nothing else turned up. But...

Problem 3: LiveUpdate was crapping out trying to install Internet Security (i.e. Norton Firewall) updates. Odd... it's a plain icon instead of the green ball. I tried running it, and though the directory and many of its files were there, it still couldn't run many functions. I tried some other icons. MusicMatch 4: couldn't find the working directories. Microsoft Word: "Please install from disc." PictureIt Express: Couldn't run. PROBLEM!

My initial guess is that the virus, AOL 9 or both screwed up his registry somehow. What I'm not sure about is whether that's a likely assumption, or necessarily what to do next.