Let's say I had a branch named coolbranch in my repository.

Now, I decided to delete it (both remotely and locally) with:

git push origin :coolbranch
git branch -D coolbranch

Great! Now the branch is really deleted.

But when I run

git branch -a

I still get:

remotes/origin/coolbranch

Something to notice, is that when I clone a new repository, everything is fine and git branch -a doesn't show the branch.

I want to know - is there a way to delete the branch from the branch -a list without cloning a new instance?

git remote prune origin 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