I can't unfollow a deleted post. This may be a regression, or a corner case which has not yet been reported.
I have very low rep on Economics (currently 105) and my "Following" tab simply says I have no questions which I follow:
And yet I have received multiple inbox notifications for a question I followed which was then deleted, and which has apparently then still been edited by its author:
I posted a question on the Economics meta and Glorfindel helpfully pointed me to Cannot unfollow locked post from Following tab but ... it doesn't work; as reported above, I don't see the post in the Followed tab.
The "solution" at How do I unfollow a deleted question? does not work; it only fixes it for users who have the privilege to see deleted questions in the first place.