Something else: Do you use VLAN-Segments on that network?
If you are on (different) VLANs, mDNS needs a repeater/reflector