TL;DR - the real answer:
$ git remote prune origin
Slightly more details:
git branch -d foo-branch
will fail to delete if foo-branch is not merged into your current branch.
It's also a good idea to clean up old branches on a remote if they've already been merged. You can do this from the commandline by git push origin :foo-branch
.
However, the old "phantom" branch foo-branch will linger for autocompleting git checkout. Apparently git is caching the branches available on the remote. By calling:
$ git remote prune origin
You can clear the local cache of what branches are available on the git remote.
I can reproduce the OP's issue for git 2.2.1 (and probably earlier versions) on OSX.