Are you using the Follow User plugin by any chance? I ran into a similar issue where deleted users would not be removed from someone’s following and notifications would get stuck in a loop. My solution was to manually remove some records from the database. The issue in the plugin has been fixed, but if you’re on an older version you might still run in to this.