I had this experience with the Klez virus on an ME machine. I took a laborious way around; there may be quicker ways.
1. disable the "restore" function in "Accessories>System Tools"
2. boot to a Command Prompt
3. navigate to the folder with the Restore Volumes.
4. delete the offending volume(s)
XP Help is unhelpful about the number of volumes it will keep and for how long. There must be limits.