A bug report about this was raised on MSE: I am still seeing notifications of edits on a post I followed, which was deleted:
Going forward, you should be able to unfollow deleted posts from both the question page itself and from the "Following" tab on your user profile.
But right now, neither the followed and deleted post nor the "Unfollow" button are showing up in my Followed posts tab. Those with the Access to moderator tools privilege will not be bothered by this problem, owing to the fact that they can see deleted posts, but those of us who don't have that privilege can't.
As the ability to unfollow deleted posts from the Following tab existed before, assuming the quote above is accurate, could we reinstate that ability?
The post this question was duplicated to is now marked status-completed, but I am still unable to unfollow a deleted post from my "Followed Posts" tab, so I'd like this to be reopened. See my answer at the duplicate for more details.