[nixgeek]

You could add the entry in your /etc/hosts file for that one Windows computer, or you could run a DNS server internally to resolve only the internal addresses. I have the same issues with my GNU/Linux systems when trying to access a Windows computer using the hostname. At work, I've modified the /etc/resolv.conf file on my GNU/Linux computers so that they could resolve the names to the IP addresses of the Windows computers. I've also modified the /etc/nsswitch.conf file to also search hostnames through DNS.

In Mac OS X, I've usually just added the DNS nameservers manually from the Network pane in System Preferences for the Macs at work if they don't get it from the DHCP server.

EDIT: Just noticed that you tried exactly what I mentioned in GNU/Linux, so you are obviously familiar with this. If you're using Tiger or earlier, remember that most everything is managed by NetInfo, so you might have to launch NetInfo Manager to make the changes. Be careful, though.....you can make some dire mistakes in there if you don't know what you're doing.