fetch from origin with deleted remote branches?

You need to do the following

git fetch -p

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