Hi Mahlon,
I did some testing and am able to replicate this behaviour. It appears that the lead (entity) record may be getting marked for deletion instead of simply being deleted as it should. A link to the lead still exists via the Entity_RecordID field even though the lead can no longer be located in the Entity table.
I have created a ticket for the development team to investigate and will keep you posted on any updates I receive via this thread.
Sorry for the inconvenience.
-Audisho