I had remote branches that would not go away even after they were deleted on the server. This tip about setting “Prune remote branches” worked for me. I found it here.
Go to Team Explorer, and click Home button. Then Settings > Repository
Settings, and set “Prune remote branches during fetch” drop-down to
True. Don’t forget to click “Update” button to save your edit.
After changing the setting I did a fetch on one of the deleted branches and all of the deleted branches disappeared.