If the device is using DHCP, and you know the MAC address, can't you go into your DHCP server and see what IP was assigned to it? Most DHCP servers keep a table that is accesible.
You'll only see an arp entry if your machine has talked to the other machine within whatever aging time is set.
Also, what type of network are you on. If you're on a Windows network, check WINS, and DNS as well. The machine may have registered itself when booting up.