fetch from origin with deleted remote branches?

From http://www.gitguys.com/topics/adding-and-removing-remote-branches/

After someone deletes a branch from a remote repository, git will not automatically delete the local repository branches when a user does a git pull or git fetch. However, if the user would like to have all tracking branches removed from their local repository that have been deleted in a remote repository, they can type:

git remote prune origin

As a note, the -p param from git fetch -p actually means "prune".
Either way you chose, the non-existing remote branches will be deleted from your local repository.

You need to do the following

git fetch -p

The -p or --prune argument will update the local database of remote branches.