Do all or any of the machines have software firewalls? You could try opening command prompt and doing a netstat /a to see which port the popup is using (when it appears) and block it if they do have firewalls.

Are there records of who uses which computer at any given time? You may be able to find out who's sending the messages.

If it's Windows messenger service and you don't need it for any other reason you could disable it.

Start>run, type services.msc then double click and disable "messenger" service.