So I realized that the Windows boxes on my LAN were not attempting to resolve LAN hostnames via the Dnsmasq DNS server running on my Tomato install. After lots of Googling, I found what I think is the best router-side solution: http://tomatousb.org/tut:configure-windows-network-browsing Basically, Tomato can run a samba/WINS server, and doing so will cause it to publish ALL static DHCP entries via WINS. I verified this by pinging a hostname defined in Tomato's static DHCP list that was not actually currently on the LAN; Windows was able to resolve it to the defined IP address. By following the guide, no special client configuration is needed. I love Tomato! Edit: See post #6 in this thread for a way to do solve this issue without using samba/WINS/NetBIOS.