At work we have an WinSBS domain at the heart of our network, which is all Windows PCs. The domain controller is acting as a DNS for these computers.

I have recently added some personal use Linux machines to the network, without joining them to the domain. I have set up Samba with "wins server" pointing to the domain controller, which lets the Windows boxes resolve the Linux hostnames just fine.

I also have resolvconf set up with the domain controller as a nameserver and the local domain as a searched domain, which lets the Linux boxes resolve the Windows hostnames just fine.

However, the Linux boxes will not resolve other Linux hostnames at all. Given that I don't have control over the DNS server (I am not the network admin) and that at least one of the Linux boxes is not an always-on machine and is likely to change its LAN IP frequently (via DHCP), what service am I missing to make their hostnames visible to each other?