... One alternate way your firewall could be broken is that it is allowing UPNP (or Apple's equivalent.. forget its name).
zeroconf fortunately doesn't do the UPnP port forwarding stuff. filtering multicast is an easy way to halt zeroconf discovery if desired anyway...