I would uninstall xoftspy. It was once listed as rogue application.
http://www.spywarewarrior.com/rogue_anti-spyware.htm.
The version I used ran off a U2 drive. I run AVG the same way. It allows me to scan my lab machines at school witout installing software on them.
Some good programs.
http://www.spywarewarrior.com/rogue_anti-spyware.htm#trustworthy
This online scan usually finds anything bad.
http://www.pandasecurity.com/homeusers/solutions/activescan/
I have used panda in the past. IIRC it found a few things that AVG missed.
I haven't got round to scanning my computer since this started happening, I'm going to do it later tonight.
I have no proof that there was anything bad on the machine. Just the weird google challange/thing/whatever.