Looking at the code, "brew prune ..." doesn't seem to actually do anything.
It should remove symlinks that no longer point to anything, it gets run after an rm to clean up /usr/local, I think it works but will check later, going out now…
rm -rf /usr/local/Cellar/git
And it removed all the links that did point to git stuff. Does this not work for you?
This works; not sure what I was missing originally, sorry.