How did you send your message to all the computers on the network? Did you use this command:
[code:1]net send * message[/code:1]
This should work even if you have messenger service disabled (Sending messages that is).
Have you tried sending messages to computers through their IP address?
As the Shout Box mentions make sure the receiving computer has the messenger service enabled!!