Since you claim you did in the OP, how did you go about deleting the feed originally? Everything I have seen while investigating this is that the option to delete is not even available to try, which would be the bug as far as I can tell.
While I suggested earlier that the cache might have something to do with it, I was mostly incorrect. The feed itself is not loaded from a cache, only the elements inside the feed. I was correct only in that successfully deleting a feed orphans the cache data. It would remain in the database meaninglessly.