How to check if an object is deleted?
I would do it by object name

def is_deleted(o):
    return not (o.name in bpy.data.objects)

# or instead of a function,
# obj will be None if the object isn't found, 
# else it returns the obj reference
obj = bpy.data.objects.get(o.name)