Apologies, it seems there was an option to cache the news feed specifically. Disabling this option fixed the issue.
I am new to XenForo and am not sure if this problem is localized to myself, thought I'd see if anyone can reproduce this problem. Basically if you follow a user, view your personalized member news feed (/account/news-feed/) then unfollow the user, they will not be removed from your personal news feed. However if you follow a user and unfollow the same user without viewing your news feed, they will not show up in it (I assume this is how it is supposed to act). Here are the steps to reproduce if the problem is not localized to my installation.
1) Follow a user (make sure they have a recent post or something that would appear in the news feed)
2) Visit your personal news feed (www.example.com/account/news-feed) You should see their recent post like you should.
3) Unfollow the same user you followed in Step 1.
4) Re-visit your personal news feed (link in step 2). Their news feed stories have not been removed from your personal view.
At first I thought it was a cache issue so I rebuilt the caches (more specifically the user caches) in the administration panel but that didn't seem to fix the issue. Hope this helps if its a bug.