Why not just implement "logical delete" and have another process sweep through a few weeks later that does any pending deletes? Then they get what they want (or closer to it), and it isn't a lot more effort.