Identifying active IP addresses that have no DNS record

How do you most easily identify the host of an active IP address on your network with no record in DNS or WINS? Our first inclination would be to run a packet sniffer to look at what protocols are running and deduce what it might be (only good if it gives off traffic), or repeatedly ping while disconnecting segments of the network to narrow the location. Our unknown host turned out to be a wireless access point that had been issued an IP address. Is there a better way?

Nmap from insecure.org can identify many systems by their TCP signature.

Traceroute can tell you the path to the device so you can identify the segment it is on.

Ethernet media access control addresses contain a manufacturer-specific ID that can sometimes help identify the device.

Time domain reflection cable meters can indicate the distance to the device along the wire.

Managed switches (SNMP turned on) can tell you which IP address is on which switch port.

To stop mystery devices from obtaining an IP address, Dynamic Host Configuration Protocol can be configured like old fashioned BOOTP to only allow IP address assignment to known MAC addresses, so unauthorized wireless access points would have more trouble just plugging into the network and working.