[derefr]

In some intranets, users might be relying on mDNS (Bonjour) or WINS (SMB/CIFS) name resolution, rather than static DNS; both of those mechanisms, by default, get resolved at lower-priority than DNS (because they're quite slow, so you don't want your computer checking them first every time), so if there's a real DNS entry it'll get used.

[X-Istence]

mDNS is actually in the list FIRST in at least Ubuntu, check /etc/nsswitch.conf.

[derefr]

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.