Avahi (zeroconf/bonjour) service in bridged VirtualBox sometimes not found outside host

I have a VirtualBox with Debian 3.2.51 guest (vcube) on Ubuntu 13.10 host (ring) with a bridged network adapter. vcube has an Avahi service configured with a vcube.local name.

I can see/ping/access vcube.local by Bonjour name, but cannot see it from other hosts on the (wireless) network. At the same time, there's a lot of wire- and wirelessly connected hosts on the network that we happily see in avahi-discover or other Zeroconf clients.

I have no access to our router and cannot know if it's blocking mDNS or not.

In iptables -vnL output, there are no entries, policies are ACCEPT and byte counts are 0 both on vcube and ring.

The same discovery problem happens for a copy of vcube VirtualBox on a totally different network.

Sometimes it just starts working - we suspect this happens when we start ANOTHER copy of vcube on a different host.

How do I diagnose or fix this problem?

I am not sure I understood your problem very well but I know bridge interfaces and UDP multicasst/boradcast can trigger some eratics behaviours. To work it around you may want to disable multicast snooping on the bridge interface:

echo 0 > /sys/devices/virtual/net/$IFACE/bridge/multicast_snooping

Though I don't know virtualbox well enough to to be sure it uses proper linux bridge utils to setup bridge adpaters...