If the deleted object is just hanging out in memory and not linked to anything it should gracefully give up it’s name and rename itself to a .xxx when you claim it’s name via your script.
Another way, which is how a lot of my frame_change script work, is to check if the object is already in exists via it’s name. Then if the object already exists and is just hanging out in memory you can claim that object as your own, link it back to the scene and not have to waste CPU time creating a new object and forcing your name upon it.
ob = someScene.objects.get(myObjName)
if ob == None:
# Time to create a new object.
# This object already exist, now I can just assign data to it as needed.