This is one of those cases where I start looking into a question, and end up finding out how little I know. So forgive me if I don't have a definitive answer but merely helpful hints. It also explains the rambling nature of my post.
Do you run your own DHCP server or does your router provide the service. There are about 3 different servers and clients that you might be using and they have different configuration files, so you might want to try more information.
Here are two DHCP howtos from the www.tldp.org
How are LAN hostnames resolved for you generally. Are you using NIS, DNS?
A dhcp client can be configured to modify NIS or DNS or smb.conf based on what the server says. However, those servers would probably use fixed address and their values wouldn't need to change. Suppose you have a linksys router for a home network. You can enter your own nameserver address and/or WINS server address (samba) in the configuration so that the DHCP server includes them when it sets up the clients on your network.
Look at the contents of /etc/nsswitch.conf. Also look at the library files matching /etc/lib/libnss_*.
grep hosts: /etc/nsswitch.conf
hosts: files dns
jschiwal@hpmedia:/usr/share/doc/packages> locate libnss
I also noticed a separate /etc/nss_mdns.conf file. If you are using samba, and running winbind, you could check if you have a libnss_winbind.so library and if so, add "winbind" before the "dns" entry. Similarily, I think that you can set up on of the samba servers to supply WINS, add it's IP address to the routers WINS entry, and if a libnss_wins.so library exists, add "wins" to the "hosts: ..." entry in /etc/nsswitch.conf file.
I'm not certain if "mdns" would supply hostname information from the router's dhcp server, or if multicast DNS is just used with apple computers and equipment.