The only problem with using arp -a is that if the machine is past the router, you will only see the MAC of the router and not the PC.
Getting the arp from the router works well.
Once you have the IP address, a simple ping -a x.x.x.x should resolve the name.
There is a freeware utility I use at the office that will scan the network and map out MAC, IP, and Machine names. I will try to remember to post the name of the program tomorrow at work.