Okay, this seems to be tough case. I would have bet it was something in your Run -folder in Registry. Though, once there was one exe, which would install the virus every time I booted my computer. The situation was so, that merely deleting the virus itself diidn't solve the problem, but finding out which was the virus' installation executalbe, deleting it and removing its key from Run -folder in registry.
However, you said there is nothing in your Run -folder, so this is to no help. However, I put here a link to one thread in computer discussion group (its in finnish), but you can see the links in this particular thread, and can follow them. Take a look, there propably is some programs you haven't tried yet.
How to get rid of banners, pop ups, etc.