Eltoshen--The Virginia Tech Antivirus website has a related page on
XP Antivirus/Antispyware 2009 and all its variations. It also includes a link to a removal program, though I'm not sure how well it will work in your case since you've already attempted to use System Restore/etc. If you haven't already seen/tried their solution, I'd give it a shot.
Good luck!
http://antivirus.vt.edu/alerts/antivirus2008.asp