In 5.0 notification-security-procs.tcl proc can_notify_user checks to see if the user state is active.
Take a look at that proc and where its called and maybe you can patch your system so it won't send notifications to "deleted" users.
You may also have to patch the bulk-mail module, does anyone know if that has a mechanism to prevent bulk mailing non-active usrers? One thing to test is if you create a spam to be sent in the future, then delete one of the users that it would have gone to, does the email get sent? It should not.
