git remote prune – didn't show as many pruned branches as I expected

When you use git push origin :staleStuff, it automatically removes origin/staleStuff, so when you ran git remote prune origin, you have pruned some branch that was removed by someone else. It's more likely that your co-workers now need to run git prune to get rid of branches you have removed.

So what exactly git remote prune does? Main idea: local branches (not tracking branches) are not touched by git remote prune command and should be removed manually.

Now, a real-world example for better understanding:

You have a remote repository with 2 branches: master and feature. Let's assume that you are working on both branches, so as a result you have these references in your local repository (full reference names are given to avoid any confusion):

• refs/heads/master (short name master)
• refs/heads/feature (short name feature)
• refs/remotes/origin/master (short name origin/master)
• refs/remotes/origin/feature (short name origin/feature)

Now, a typical scenario:

1. Some other developer finishes all work on the feature, merges it into master and removes feature branch from remote repository.
2. By default, when you do git fetch (or git pull), no references are removed from your local repository, so you still have all those 4 references.
3. You decide to clean them up, and run git remote prune origin.
4. git detects that feature branch no longer exists, so refs/remotes/origin/feature is a stale branch which should be removed.
5. Now you have 3 references, including refs/heads/feature, because git remote prune does not remove any refs/heads/* references.

It is possible to identify local branches, associated with remote tracking branches, by branch.<branch_name>.merge configuration parameter. This parameter is not really required for anything to work (probably except git pull), so it might be missing.

(updated with example & useful info from comments)