Adware problem

My computer is driving me nuts cause i get a popup every 20 minutes saying I have malicious programs and that i need to go to regfix.com to download a repair. This is obviously an advertising scheme, but i can't get rid of it. I've tried ad aware, spybot, AVG antivirus, and hijackthis!, but it wont go away. I did all of these while in safe mode with my system restore off. Any Help?

microsoft.com-
anti spyware beta.....just cause shes got a sweet body.

[Blarg]

How about Microsoft Anti-Spyware?

Are all your definitions up to date? I got this kind of thing before, but it's gone now.

P.S. If you're not using Firefox or some other non-Explorer browser, switching away from Explorer will get you away from a lot of these problems.

Does the popup say "messenger service" along the top of the window?

If so, shoot the messenger.