Not Difficult (Score 1)

It might take some time, but with managed switches and SNMP it is possible to pull the bridge tables off of each switch as well as ip to mac correlation from the routers. The switches/routers know where the device is or you would never see it on the network. You just have to know how to make the switches tell you. Even if it's on a virtual machine you will know what switchports are forwarding for what mac addresses which will narrow down the search quite a bit.