Hit F8 a couple of times as the motherboard manufacturer screen comes up (ie the first screen that you see, before the WinXP boot screen).
You'll then get a couple of options in DOS - "Safe Mode", "Safe Mode with Command Prompt" etc - just choose normal old Safe Mode.
The PC will boot and start as normal, but displaying "Safe Mode" in each corner of the screen. There will also be a prompt asking if you want to work in Safe Mode - just click yes.
In Safe Mode, a whole host of windows applications and drivers are not loaded, so some things won't work - your modem, for example. However, just browse to the files where you've got your AV/Spyware stuff installed and scan from there, as not all your icons will ness. appear on the desktop.
The fact that system restore isn't working is a bit odd, but run through the scans first and go from there. Does it give you a particular error message as to why it can't restore? If so, google it and you'll probably find some answers.
EDIT : see if you can run SystRestore from Safe Mode, too. Sometimes it helps.