Interesting. I think that where things start to get gray is when a.) There's a collective vs. individual action/response involved (even in the cases that are defined as "not a government") and b.) when the "crime" involved is not as clear cut as, say outright theft. In the latter case, someone has to define what's acceptable for a given community (i.e. laws) and all parties must agree to it.
And, of course, there then must be some form of "policing" as well as an agreed upon penalty when a violation occurs.
>if you force random people to pay for the incarceration of the thief, that makes you a government.
The people who pay in a "democratic" society (presumably via taxation) aren't random, right? In theory, they have an interest in laws that, say, prevent theft of their property. Likewise, in a community like SR2 people are "forced" to pay via additional fees that SR2 must levy (whether stated explicitly or not) in order to police, prosecute, etc.
>if you exert some kind of retributive justice on the thief, like, take all stuff from him, and shoot him in the back, that makes you a criminal (by definition, not necessarily in the eyes of the people),
I'm not sure how we get to a definition of what's criminal without it referring back to what's acceptable to "the people". Again, we can hold out things that appear to be obvious (like theft), but even that can be gradated.
I'm not trying to split hairs. In fact, it seems that some of the definitions of libertarianism seem to do just that when drawing contrasts with other forms of government. It all sounds great when speaking on an individual basis, but whenever collective activity is involved (as it invariably will be), it seems to break down. That is, something is needed that at least approximates a form of what we'd recognize as government.