1) Muggings - If you get mugged by someone you know, it's very easy to find them and punish them. It's no coincidence that muggings tend to happen in big cities where the chances of a mugger attacking someone they know is very low (anonymity).
2) Sexual predator - If a priest rapes a child and the child tells people about it (i.e. removing some of the priest's anonymity regarding his actions) the priest is likely to be investigated and thrown in jail. If you know a sexual predator lives next to the school your kid goes to (i.e. he has lost some of his anonymity) you might take additional protective measures that could prevent your children from being assaulted. Whether this is the most common scenario, or whether it is fair for sexual predators to be publicly identified, are completely separate issues. I am simply illustrating a cost.
3) Terrorists - If you were the pilot of a plane and knew that some of your passengers were members of an extremist group that had plotted to destroy airlines in the past (i.e. some of the passengers had lost some of their anonymity) you would probably kick them off your plane. Whether or not this relates to 9/11 is not the point, this is simply an example of a cost of anonymity.
As for your last point: I never said the costs of anonymity outweigh the benefits, I simply showed that there are costs.