The short answer is to host public discussions of the new rule.
The ability to collectively discuss problems and rules that limit negative behavior plays a big role in setting new community rules. Your job is to encourage users to initiate public discussions about any violations they see in the community, and then do your best to make sure that the community takes the right direction in solving the issues. Consensus obtained through public discussions in which anyone can participate has great weight and legitimacy. Users and volunteers will internalize such decisions, follow them and force others to follow them as well without any effort from your part.
This is a fragment of a draft of the book “Lessons Learned While Working On Stack Overflow”. Read the full book on kindle or the paperback version.