Hmm.. had a virus once that actually reinstalled itself on startup. Basically, everytime I'd start up, AVG would alert me of the same virus and clean it.

What I found (after like 2 hours of troubleshooting) was that there was a program on startup that was creating the virus everytime - but wasn't actually a virus in and of itself, so nothing was detecting it. Deleted it, problem solved.

If anyone else has the same problem, check MSCONFIG and see what's going on at startup, and check anything that looks suspicious - if you get a virus warning, you've found your EXE. The EXE probably won't show up on a virus scan, you might have to actually RUN the thing to find it.
------------------------------------