Such approach invalidates any attempt to compare previous state and current state of a record in a table

If a previous value has meaning, it should never have been deleted. Also, in most schemes, PK re-use come some time after its original use.