In a user's mail file, they should be disabling a mail rule before deleting it. That's because the actual ruleset lives in the CalendarProfile document and you have to update this ruleset by using the enable/disable buttons in the mail rule view. To get rid of an old rule that is still running, add a new rule, then use the view buttons to enable/disable it. Then delete the rule and all rules should be disabled.