After deleting branches on github, or any other tracked remote, you can remove references to deleted branches without having to fetch changes by simply using the remote prune sub-commands:
$ git remote prune origin
Another remote:
$ git remote add bitbucket git@bitbucket.org...
$ git remote prune bitbucket