It's more likely to be a dynamic update DNS issue; Windows clients, beginning with Windows 2000, automatically update Windows DNS servers directly with their new details once they've been leased an IP address by the DHCP server. This way, the DNS and DHCP servers are kept in sync. Macs don't. Previous posters are correct when they say that the Macs are getting these incorrect hostnames from the DNS server. The problem, then, is with the DNS server.
I haven't used the current Microsoft DHCP server but previous versions provided an option specifically for this situation. Instead of the client machine talking directly to the Windows DNS server, as happens automatically with Windows 2000 client and later, the Windows DHCP server can update the Windows DNS server once it has successfully leased an IP address to a client.
You need to enable the option yourself in your Windows DHCP server. The wording for this option will usually be something like "Always Update DNS and Enable Updates To DNS Clients That Do Not Support Dynamic Update".
You might still find this article useful, though it's for Windows Server 2000 DHCP. (I'm not having a good Google day.)
OK, after a long time trawling the Internet and trying to read through man pages, I mostly figured out what's going on:
[H]ow in the heck did it know to send
the server's real hostname if the
configuration isn't set up to send it
in the first place?
Apparently, send host-name "<hostname>", and more specifically, <hostname>, has special significance on Ubuntu. It tells dhclient to send your machine's current hostname to the DHCP server. Note that this is case-sensitive (i.e. if you type <HOSTNAME>, dhclient will send the literal text <HOSTNAME> to the DHCP server). As reported here and here, this works on Ubuntu Feisty and above, being part of a patch to (ironically) fix a problem with dhclient not sending the machine's hostname by default.
[W]hy did the first DHCP lease (for the
old network) not include option
host-name, but the second DHCP lease
(on the new network) did include it,
if I haven't touched any of the
configuration files?
This just seems to be because not all DHCP servers will echo the hostname back to the client. Yesterday we still using a Linux-based ClarkConnect router as our DHCP server, which echoed the hostname back to each client. Today we disabled DHCP on that server, and switched to using the built-in DHCP server on our primary domain controller. Our DHCP leases from the PDC don't include option host-name either, but it doesn't seem to affect anything. The machines get updated in DNS, and they can all find each other by hostname.
When I run hostname, the server
returns fozzie.our.domain, but
dhclient.eth0.leases says the hostname
option was set to fozzie (no domain).
How did it know to strip off the
domain?
This is me not fully understanding the intricacies of DHCP. Our DHCP server was set to configure all of our clients with our domain. I'm guessing the DHCP server was smart enough to remove the domain name portion from the hostname sent by the client.
Anyone have any corrections or clarifications to add to this answer? It still seems a bit "hand-wavy", so I won't accept it as-is.
Best Answer
I'd say the problem is on the DHCP server end rather than your MacBook. The Windows DHCP server has a number of options for updating DNS records, and can behave a bit differently for clients that are or are not members of the domain. In the Windows 2003 version, there is a checkbox for updating clients that do not request updates (It mentions NT clients). From memory, I think that is what you will need to ensure is checked.