Hate to bust the ol' bubble, but System Restore is where alot of viruses hide themselves.
Use a program like HijackThis! and post the log file here.
I'll tell you which regfiles to delete, then run
Housecall to finalyl get rid of any remaining debri.