Given access to separate two Xen instances running Linux, is there some way to identify if the two instances are running on the same physical machine?
No. Anything you can try can be faked by the hypervisor. Even if you're not running in a hostile environment, the hypervisor blocks all of the interesting hardware calls you can make normally (
You're trying to answer the wrong question, though. Any possible scenario I can imagine this being useful in is better solved with either comprehensive system monitoring or contractual guarantees with visibility of compliance.