Visual Studio stores them in a local cache.
You can run the following from the command line, then whenever you make a selection from the synchronization menu in Team Explorer, the branches will be trimmed:
git config remote.origin.prune true
It looks like it should be installed by default!
, :
git config --global remote.origin.prune true