Hi dagul,
The cleanup icon is temp files cleaning. No harm if you want to do it, but utilities like CCleaner are faster and more thorough.
The Protection icon is for malware. There are better online scanners like Kaspersky, BitDefender, and F-Secure. You've tried them all, and I doubt if Windows Live will catch anything else.
Tuneup is basically to defrag your hard disk. You can do this yourself periodically. Won't make much of a difference to a NTFS file system, though (which most of us with XP have).
Just clean the registry first, then do a clean up, and then a tune up. Then scan with Panda and see if the malware reg entries still exist or not.