Consider an user who has chosen to be notified when he or she receives a private message.
If another user sends a pm to the first one, and removes it before the recipient logs in the board again, there is no notification for the first member.
However, if the private message is automatically deleted by the first user due to a defined rule (in his or her UCP >>> Rules, folders & settings), there IS a notification when he or she logs in the board again. If he or she clicks on the notification link, an error message appears (private message could not be found).
It would make much more sense there is no notification for both situations.