This is a common use-case for me, I clone a repository, checkout a branch, do some code changes, make multiple commits, then when it's stable, I do a push to remote, eventually the branch gets merged and deleted, and I'm left with a local branch with upstream gone.
I was looking for a safe way of deleting all such branches. From the description, it seemed like git remote prune origin is doing this exactly. But it doesn't seem to be working for me.
Seeing the following behaviour, the branch encrdb_init has been deleted from remote but the git remote prune origin command does not seem to prune it. I am not sure why.
$ git branch
  bugfix/encrdb_init
  * master
$
$ git remote prune origin
$
$ git checkout bugfix/encrdb_init
  Switched to branch 'bugfix/encrdb_init'
  Your branch is based on 'origin/bugfix/encrdb_init', but the upstream 
  is gone.
  (use "git branch --unset-upstream" to fixup)
$
$ git branch
  bugfix/encrdb_init <<< shouldn't this have been pruned?
  * master
for reference adding output of git remote show origin
$ git remote show origin
* remote origin
  Fetch URL: <redacted>
  Push  URL: <redacted>
  HEAD branch: master
  Remote branches:
    SSL_test                                                  tracked
    addNodeFix                                                tracked
    autoprefix                                                tracked
    release/1.0.2                                             tracked
  Local branches configured for 'git pull':
    bugfix/encrdb_init          merges with remote bugfix/encrdb_init
    master                      merges with remote master
    release/1.0.2               merges with remote release/1.0.2
  Local refs configured for 'git push':
    master                 pushes to master                 (up to 
date)
    release/1.0.2          pushes to release/1.0.2          (up to 
date)
$ git branch -vv
* bugfix/encrdb_init          341a078c [origin/bugfix/encrdb_init: gone] <redacted comment>`
 
     
     
    