Git remote branch deleted, but still it appears in 'branch -a'

git remote prune origin, as suggested in the other answer, will remove all such stale branches. That's probably what you'd want in most cases, but if you want to just remove that particular remote-tracking branch, you should do:

git branch -d -r origin/coolbranch

(The -r is easy to forget...)

-r in this case will "List or delete (if used with -d) the remote-tracking branches." according to the Git documentation found here: https://git-scm.com/docs/git-branch

Try:

git remote prune origin

From the Git remote documentation:

prune

Deletes all stale remote-tracking branches under <name>. These stale branches have already been removed from the remote repository referenced by <name>, but are still locally available in "remotes/<name>".

With --dry-run option, report what branches will be pruned, but do not actually prune them.