I would check for a record delete step somewhere that is inadvertently operating on the wrong TO.
For example if you do a GTRR to go to some related records and then do a delete to delete some records on the target TO of the GTRR, if the GTRR fails (there were no related records) then you will still be on the originating TO. If you now do a delete record, you will actually be deleting the record in the originating TO. You must always check that you have arrived at the correct target TO before doing a delete record.
Index files can get corrupt and make the record appear that it has been deleted. You can run recover on the file to rebuild the indexes. If anything else beside the indexes are corrupt in the file then you need to use a backup.