"but now even that doesn't spot it (when running a scan). "
So its not there then.
It is a virus of sorts click here (its actually a Porn Dialler)
AVG should sort this one. I'd suggest update AVG, boot into Safe Mode and scan with AVG and then AdAware (make sure thats up to date too) then you know you are clean.