It sounds like a process is listening for when you connect to the internet and is then, as you say, connecting to that site.
Where is this message displayed? Is it a standard windows message (which would be odd as it's not normally bright enough to warn about that sort of thing) or from a personal firewall if you're running one, or what?
I would also recommend investigating your add/remove programs list to see if anything suspicious has inserted itself in there. If other people have access to your computer (or if you've accidentally clicked "yes" on one of those goddamn ActiveX Install boxes that certain sites throw at you) then there could be one of the porn dialer type thingies installed.