I have had very good success adding these columns to all my tables (all with simple indexes)

cUserIns Char(24)

tDtIns DateTime

cUserUpd Char(24)

tDtUps DateTime

cUserDel Char(24)

tDtDel DateTime

iDel Int

default value for iDel is 0, default value for tDtIns is getdate().

When any user does a delete, put a 1 in iDel and put the name and datetime in cUserDel and tDtDel. Now you know when and who deleted the row. For all your SQL, append at the end of every where clause " and where iDel=0". Now no row is truly deleted and if you need to get it back, you can. Very little overhead, and if you include these columns in your table planning from the beginning there is no extra work.