By default the Visual Studio Team Explorer does not refresh the remote branches when you fetch updates from the server. The fix for this is pretty easy, you need to set "Prune remote branches during fetch" to true in the "Git Settings". You can do this in the global settings or per repository.

  1. Go to Team Explorer settings
  2. Select either "Global Settings" or "Repository Settings"
  3. Set "Prune remote branches during fetch" to true
    Prune remote branches during fetch

And your done, now the remote branches will be updated every time you fetch or pull.
The only thing I don't understand is why "Prune remote branches during fetch" is not the default behavior.