Perhaps it isn't a virus, but a very nasty spyware or something. Obviously if you said you turned off system restore, and booted into safemode, and scanned with AVG using the latest definitions, and it STILL doesn't find it, it isn't a virus, or at least its highly unlikely. Either that, or AVG is just missing it. Try another AV Program, such as Norton, or better yet, NOD32.
Have you run Adaware/Spybot/Spysweeper/CWS Shredder?
Also try running the System File Checker. in the "Run" box, type: "sfc /scannow" and replace any file it says is corrupt.
It is possible that someone has really screwed around with your computer via way of the trojan. If you still can't get rid of them, it might be best/safest to reformat and cut your losses.