Ping is not a broadcast protocol, so that's not much of a proof.

Is the machine that you are sending from on the same subnet as the machine you are sending to?

The problem is that there is a specific NetBIOS name for the messenger service. If you cannot resolve the messenger NetBIOS name you cannot send the message even if you can resolve the IP address.