Supondo que o projeto tenha muitos ramos
$ git branch -a
* master
remotes/origin/HEAD -> origin/master
remotes/origin/master
remotes/origin/other-branch
quando em remoto um branch é removido, seu projeto mantém este branch em um histórico de branches remotos
$ git push --delete origin other-branch
$ git branch -a
* master
remotes/origin/HEAD -> origin/master
remotes/origin/master
remotes/origin/other-branch
para limpar os ramos antigos da sua listagem, você pode fazer
$ git remote prune origin
* master
remotes/origin/HEAD -> origin/master
remotes/origin/master