I have a home network with a few Linux boxes and a Windows XP laptop. I shut down a CentOS machine, removed the hard drive, installed a new hard drive, and then started a clean install of Ubuntu 12.04. When it came time to set the hostname, I entered the same hostname I'd been using for this machine, and the installer warned me that there already was a machine with that name on the network. How did it know that?
All of the machines (except that XP laptop) have fixed IP addresses, with all of the addresses listed in all of the /etc/hosts files, so there's never any nameserver lookups for these machines. Also on the net is a DSL modem that runs DHCP, and a Linksys wireless router configured to just be a wireless access point, no DHCP, and with an IP address that doesn't conflict with the DSL modem.
It's also true that the XP laptop has the IP addresses listed in I forget which file, so that it doesn't do nameserver lookups for my home machines either, but I don't think that that laptop was even running when I did the install. The installer was happy to let me insist on using the hostname I wanted, but I'm really curious to know how this information was available to the installer.
Based on a launchpad entry it appears that avahi may perform a scan of the network. http://bit.ly/1eqBSRr
If I was going to do it as a user, I'd be using nslookup to confirm the local name server didn't have an entry for the host.