I have a Linux server running ISC DHCPd and BIND DNS. Clients that receive their IP from DHCPd sometimes seem to update the DNS with their DNS info., but sometimes not. Any ideas why this might occur?
Identifying the clients (Windows, 'nix, etc.) would help provide a better picture, as well as the DNS server in use.
It sounds like you may have mixed Windows (maybe across multiple versions) along with other OS types in your environment.
Within Windows, against Windows DNS (since Windows 2000), the DNS tab within the TCP/IP "Advanced..." properties - there is a check-box option to "Register this connection's address in DNS" for what you are describing.
In addition to Windows 2000+ DNS servers, the functionality also exists since version 9 of Bind, so this is also available on non-Windows platforms meeting this requirement as well.
Also on Linux, you may also need to tell the DHCP client to send the hostname along. For example, on debian, you will need to edit /etc/dhcp3/dhclient.conf with the following settings: