Switching off System Restore should stop them being protected and restoring (no idea why it didn’t), reboot and check if clean, if so then enable System Restore. Check out the link below just to be sure.

Win XP-ME - How to disable System Restore