After even some more info:
MainRepo -> PublicBareRepo (with a lot of junk) -> The World
So the problem is here. Once in a while you do a push from MainRepo to PublicBareRepo, which now contains stuff that are no longer valid and shouldn't be there. In the future, make sure that you only push up branches that should be there. I guess the main thing now is to remove branches from it, and then I have to step back to my original answer (assuming we are talking about the same kind of junk)
git push PublicBareRepo :someBranch1
git push PublicBareRepo :someBranch2
After some more information from the OP:
It seems it's the repo design thats causing problems and a --mirror is the way to solve this. If A is the main bare repo that devs are pushing their stuff to, and if B is a public bare repo, then B should be a clone of A with the --mirror option.
What needs to be done is to do "git remote update" (assuming B already is a mirror of A) on B so it will update itself to again be identical to A.
Original answer:
If you want to remove a branch on the remote repository you can do:
git push origin :branchName
The same goes for any ref really, e.g. for a tag:
git push origin :tagName