Object rename detection
Pointer property

Use a simple collection property with a name and a pointer to an object

import bpy

from bpy.props import CollectionProperty, PointerProperty

class ObjCollection(bpy.types.PropertyGroup):
    object = PointerProperty(type=bpy.types.Object)

def register():    
    bpy.utils.register_class(ObjCollection)
    bpy.types.Object.foo = CollectionProperty(type=ObjCollection)

if __name__ == "__main__":
    register()


I've added the foo collection to every object... now off to the python console to test, clear the objects list

&gt;&gt;&gt; C.object.foo.clear()


Load up every object in scene to context objects "foo" collection

&gt;&gt;&gt; for o in C.scene.objects:
...     item = C.object.foo.add()
...     item.name = o.name
...     item.object = o
...     


Rename every object in scene to "Bar"

&gt;&gt;&gt; for o in C.scene.objects:
...     o.name = "Bar"
...     


Iterate over context object foo

&gt;&gt;&gt; for o in C.object.foo:
...     o.name, o.object.name
...     
('Cube', 'Bar.001')
('Lamp', 'Bar')
('Camera', 'Bar.002')


The object formerly known as "Cube" is now known as "Bar.001" etc.

If the object has been since removed then 

C.object.foo["Lamp"].object is None


We know that the lamp,  "Bar" formerly named "Lamp"  has been removed.

Please note: have defined the properties on classes eg bpy.types.Object and then deal with instances eg context.object.  In your question code it appears you have monkey patched a list onto the class bpy.types.Object (the one and only...) instead of, as shown in above,  the instances of that type (many)