Oh and another one: avahi (which implements zeroconf)
Really. for small to mid size networks, avahi makes managing IP addresses a thing of the past. Just give the machine a name then "aptitude install avahi-utils", then you can "ssh newhost.local" without ever needing to know the IP address. I saw someone above mention dhcpd over static IP address - that's fixing exactly half the problem. Avahi fixes the other half.