You're sure you disabled the Windows Messenger service and not the Instant Messenger app
 
To verify, click on the Start button, then select Run and then type in services.msc followed by the OK button or the enter key.
 
Now scroll down the list until you see Messenger. You want to stop the service if it's running and then change the startup type to disabled and not just manual.
 
If it is already disabled then the pop-ups are coming from either java and/or activex scripts and they are meant to look like the messenger service notification windows.
 
In this case some other background pop-up ad killer is needed.

I had these Windows Messenger Service pop-ups occurring. They were incredibly annoying.
 
Assuming you're using Win2K or WinXP, go to Administrative Tools in the Control Panel. Then go to Services. Click and highlight 'Messenger'. Right-click and select Properties. Set 'Startup type' to Disabled. Press the Stop button. Exit Services and Admin Tools.
 
I found that you had to DISABLE Startup type, rather than just setting it to Manual.

I had it disabled, yet still got them. Nothing like being in an online game and getting blown out cuz of these! I used Spybot Search & Destroy last night. So will see if that helped any . . . . .

If you're are a network it might to useful to have access to Messenger, however, it is annoying when you get spammers using it too. So simply activate the built-in firewall on the network connection that has access to the internet. That will stop the spammers.

No, this is my home computer on Earthlink DSL.