Logging: Build upon the current system to log the same fields for adding records and deleting records. Record the fields that are records for changes. Possibly, expand the logging system to also record changes to an external logging process (syslogd for example).
Yes, I remember one time it would have been nice to see history for deleted sales orders.
Where a salesperson was using orders to generate a price list. He would then delete orders if a sale was’t realized. Took a couple days to unravel inventory/PO supply problems due to demand from those deleted orders.