Consider this, if you don't actually delete records but add a field to mark them as deleted, you can get the user from the last modified. If you want to actually delete records then, you can havea nightly job that deletes in a batch not one at time. This could even be set up to flag if too many records are being deleted and not run.
The easiest way to do this so that nothing breaks is to rename the table, add the column IsDeleted as a bit field and then create a view with the same name the table was orginally called. The view will select all the records where isdelted is null.
Don't let anyone talk you out of using triggers for this. You don't want people who are doing unauthorized changes to be able to escape the auditing. With a trigger (and no rights to anyone except a production dba to alter the table in any way), then no one except the dba can delte without being audited. In a typical system with no stored procedures to limit direct table access, all too many people can usually directly affect a table opening it wide for fraud. People committing fraud do not typically use the application they are supposed to use to change the data. You must protect data at the database level.
When you write your triggers make sure they can handle multi-row inserts/updates/deletes. Triggers operate onthe whoe set of data not one row at a time.