Given its IP, how can I find out the name of a Windows PC on my network?

I'd like to find out the computer name of a Windows PC (like the name shown in the 'Shares' section of the Finder, e.g. bill-pc) given only its IP address. nslookup doesn't do the trick.

I'm also interested in the reverse lookup: given its Windows name, how can I find out its IP address? ping bill-pc or ping bill-pc.local seems not to work in some cases.

If you're using Lion, you can use smbutil:

usage: smbutil [-hv] subcommand [args]
where subcommands are:
 help       display help on specified subcommand
 lookup     resolve NetBIOS name to IP address
 status     resolve IP address or DNS name to NetBIOS names
 view       list resources on specified host
 dfs        list DFS referrals
 identity   identity of the user as known by the specified host

For example (assuming 192.168.1.9 is a valid IP on your network):

smbutil status 192.168.1.9
smbutil lookup bill-pc

If you're using Snow Leopard, you should be able to use nmblookup:

nmblookup -A 192.168.1.9
nmblookup bill-pc