Interesting question.
The problem is, since you don't have the IP address or the subnet mask your basically shooting in the dark. I don't know any utility that will show you the IP of a device by it's MAC address.
What kind of device are we talking about here? Some of that stuff has support for NetBEUI or IPX or something so you can connect to it in case you lose the IP address.
Anyone else got any ideas?