As punishment can be essential to cooperation and norm maintenance but costly to the punisher, many evolutionary game-theoretic studies have explored how direct punishment can evolve in populations. Compared to direct punishment, in which an agent acts to punish another for an interaction in which both parties were involved, the evolution of third-party punishment (3PP) is even more puzzling, because the punishing agent itself was not involved in the original interaction. Despite significant empirical studies of 3PP, little is known about the conditions under which it can evolve. We find that punishment reputation is not, by itself, sufficient for the evolution of 3PP. Drawing on research streams in sociology and psychology, we implement a structured population model and show that high strength-of-ties and low mobility are critical for the evolution of responsible 3PP. Only in such settings of high social-structural constraint are punishers able to induce self-interested agents toward cooperation, making responsible 3PP ultimately beneficial to individuals as well as the collective. Our results illuminate the conditions under which 3PP is evolutionarily adaptive in populations. Responsible 3PP can evolve and induce cooperation in cases where other mechanisms alone fail to do so.