Right, wrong example perhaps ;-) In fact in the real cases where I've used it the object ref is a hash value, not a key. Does that make any difference?
Remember rule one...
Comment on Re^2: Storing object references internally
Yes it sure does. In hash values, references remain references, so your object won't ever go away.
One thing you can do, is use a weak reference in the common data structure. That way, it'll be wiped when the object goes away.
Weak references can be created using weaken() in Scalar::Util. Be sure to keep the vital link to your objects a strong reference (= not weakened), because if all you have left is weak references, the object will go away and all those references will become undef.