The default options for git fetch (and consequently git pull) do not prune deleted remote branches. I’m not sure what the logic behind this default is. In any case, to prune deleted remote branches, either fetch with
git fetch -p
or run
git remote prune [-n] <name>
explicitly. With the -n flag, it will report which branches will be pruned, but not actually prune them. See git-fetch(1) and git-remote(1) for more information.