The problem is much easier, when you want solve this for specific object categories like cup-plate-spoon instead of any generic pair of objects. Also in my opinion there degeneracies as mentioned by DaemonMaker is not going to happen in this case since we have depth image instead of just a 2D image.
When you know the objects in scene and you have a depth image, it is possible to estimate the full 3D orientation (pose) of each of those objects. If the objects in question are rigid, some sort of ICP may be enough in getting this pose. For harder scenarios where the object is non-rigid (humans) or you don't know the exact specific model of the object (say tea cup vs coffee cup), you should refer to some computer-vision/Kinect literature.
Once you have the 3D poses of the objects, answering object-object 3D positional queries will be easier.