Ran into this problem today for branches reported by git branch -a and look like this one: remotes/coolsnake/dev, i.e. a local references to "remote" branches in registered git remote add ... remotes.
When you try
git branch -d remotes/coolsnake/dev
you'll get the error: branch 'remotes/coolsnake/dev' not found.
The magic is to remember here that these are references and MUST be deleted via
git update-ref -d remotes/coolsnake/dev
(as per https://superuser.com/questions/283309/how-to-delete-the-git-reference-refs-original-refs-heads-master/351085#351085)
Took a while to uncover my mistake and only the fact that TortoiseGit could do it led me on the right path when I was stuck. Google DID NOT deliver anything useful despite several different approaches. (No that I've found what I needed there's also git: How to delete a local ref branch?, which did NOT show up as I had forgotten the 'ref' bit about these branches being references.)
Hope this helps someone else to get unstuck when they're in the same boat as me, trying to filter/selectively remove branches in a repo where some of them are present due to previous git remote add commands.
In a shell script this then might look like this:
#! /bin/bash
#
# Remove GNU/cesanta branches so we cannot accidentally merge or cherrypick from them!
# 
# commit hash is first GNU commit
R=218428662e6f8d30a83cf8a89f531553f1156d25
for f in $( git tag -l ; git branch -a ) ; do 
    echo "$f"
    X=$(git merge-base $R "$f" ) 
    #echo "X=[$X]" 
    if test "$X" = "$R" ; then 
        echo GNU 
        git branch -D "$f" 
        git update-ref -d "refs/$f" 
        git tag -d "$f" 
        #git push origin --delete "$f" 
    else 
        echo CIVETWEB 
    fi
done