Pues despues de realizar el borrado del registro mandas el mail de esta forma:
Código PHP:
$clausula = "DELETE FROM tabla WHERE condición";
$res = mysql_query( $clausula );
mail(); // aquí iran los datos del mail avisando los datos que fueron borrados
Si no sabes como utilizar la función mail() checa este enlace:
http://www.php.net/manual/es/function.mail.php
Bueno pues ya sabes las rutinas que se hacen antes de esto (conexion, seleccion de base de datos, etc..). Ahora, otra opción sería: si los trabajadores están logeados, cuando hagan el borrado del registro mandar el id del trabajador y en un campo de observaciones o algo así guardar los datos que te interesa saber que borro, para esto crea otros campos o una tabla en donde guardes esto.
Espero haberme dado a entender y que esto te sirva por lo menos para darte una idea. Suerte
