Can you customize the "Deleted" message?

There is only support for this in Notes 4.6.
A workaround is to create a delete check box in the document and let the $$QuerySaveAgent do the work.

Applies to Notes Versions: 4 4.5