Linux's mDNS support is split into two parts--mDNS presence (which uses cached/recently broadcast-announced values), and mDNS resolution (which doesn't.) If you don't have a name cached, the first part won't know about it, so you'll hit DNS lookup before failing back to full mDNS resolution. Basically, it becomes a race condition of when you last brought the machine up.