You could have a table that covered when things where deleted. 

[Deletes](Id, FromTable, DeletedId, DeletedOn)

-Josh