As you said Plus! wasn't installed at that time so it can't be the sponsor. I still somehow think it's the MSN Messenger one..but it could have come with anything really (new software...a wrong click somewhere on the net...who knows).
Try this:
http://lop.com/new_uninstall.exe
Keep your internetbrowser closed (full exit) when you are running it, prob should be solved afterwards