Policing is regarded as an important mechanism for maintaining cooperation in human and animal social groups. A simple model providing a theoretical overview of the coevolution of policing and cooperation has been analyzed by Frank (1995, 1996b, 2003, 2009), and this suggests that policing will evolve to fully suppress cheating within social groups when relatedness is low. Here, we relax some of the assumptions made by Frank, and investigate the consequences for policing and cooperation. First, we address the implicit assumption that the individual cost of investment into policing is reduced when selfishness dominates. We find that relaxing this assumption leads to policing being favored only at intermediate relatedness. Second, we address the assumption that policing fully recovers the loss of fitness incurred by the group owing to selfishness. We find that relaxing this assumption prohibits the evolution of full policing. Finally, we consider the impact of demography on the coevolution of policing and cooperation, in particular the role for kin competition to disfavor the evolution of policing, using both a heuristic "open" model and a "closed" island model. We find that large groups and increased kin competition disfavor policing, and that policing is maintained more readily than it invades. Policing may be harder to evolve than previously thought.