You were right - the simplest solution was to re-format and re-install. Painful, at a large part of a day, but ultimately the only real solution.
She says she owes me...
The number of "help a friend" jobs that I've done, where I've spent 20+ hrs trying to fix a system (becuase of malware) is incredible (and I know many of us here have done this).
At least now I worked out how to identify when it's best just to start over...
But my favourites are either bad drivers (HP all-in-one printers come to mind) or malware that hooks into the system so deeply (eg the TCP/IP stack, etc), that removing the malware incorrectly results in a dead system...
FYI - I ran into 2 of these last month, TCP/IP functionality totally destroyed by spyware crap (Ad-aware found 850+ items on one of these systems) Even after removal of bad things, TCP/IP still doesn't work.
After some research I finally resolved it by repairing the TCP/IP stack with this cmd:
netsh int ip reset resetlog.txt
Google for "reinstall tcp/ip windows xp" for more information.
From what I read, this should have fixed the non-connectivity issue, but it didn't, next I copied over the registry settings from a working XP machine:
After this I may have run the netsh command again before it worked, but I don't remember.