lol, I only asked because I caught a piece of malware a few weeks ago that was an absolute beast to remove (and I'm an advanced user). Doesn't sound like the same one, though.
Did you remember to scan all your data before restoring it? Which version of Windows do you have? With Vista and Windows 7 you must completely rebuild the hard drive. Delete all the partitions. Vista and 7 create a small partition for system restore data. And these virus like to hide there. I think XP SP3 might also do the same thing.
Im using xp64 sp2, I did scan my partitions using eset but nothing turned up. Currently scanning with spybot, seems to have found it.