OMG, sorry to hear what happened Jack... I'm not sure this would help, just a couple of ideas probably you already tried.
First, I'm sure you know regcleaner - I mean this one:
The important part now is not the regclean, but the software part - it has a list of the softwares on your puter, you might check it out, maybe you can see something that should not be there... (if ad-aware could not find it, I think its regclean part would not find those buggers either...) I'm often puzzled by some stuff I have on my puter, which I would not know of were it not for that list...
The other thing that occured to me is to run Evidence Eliminator with safe restart mode... Its easier than to back up those 30 gigs... Something tells me that EE should help...
Then there is this amazing page MikeHunt posted in bytebits:
http://www.cexx.org/ (Counterexploitation) - I was reading some stuff they wrote there, you might want to take a look, they have good advices for situations like yours, with step by step description of what to do... scroll down and "How to remove StartUp Spam" would be your section I guess... But there are many related topics...
I hope some of this would help...
ps - and don't upgrade to XP ... yet.
edited to relocate image ...