First Principles: Another way to get at anarchy, is to imagine Locke's state of nature then see what evolves. In the state of nature, everyone is perfectly free to do what he wishes, but nonetheless people have their instinctive sense of property, and of justice. Most people will therefore refrain from obviously hurting each other, or taking each other's obvious property. But some people won't - natural "criminals" if you will. People can punish each other if they will; though most normal people will only punish if they feel wronged. But again, there will be a minority who may claim that they are wronged by others and proceed to punish them, even though there is no wrong.
Now, there are several fairly obvious and large problems with the state of nature as thus far described. One is, it seems that the strong can terrorize the weak. A second is that, justice is haphazard even among equally strong peers. A third is that feuds are possible. I am sure you can imagine others. Locke jumped pretty much directly from this point to a social compact to create the state. That's fine as far as it goes, which is exactly to the next generation, or until someone wants to withdraw. At which point you either assert "sovereignty" and tell the non-member to join or die, or you have a state of nature again (at least for that one person; and the problem will grow as others join him).
Can these problems be solved without a state? Fairly easily, yes. People can band together to form mutual aid groups, or protection societies. If one member is attacked or harmed, the others pledge to help, and viceversa. Division of labor always works in capitalism, so these agencies will likely specialize into "cops" and customers, for most day-to-day functions. Adjudication is still a problem, but that can be solved too. People with a good reputation for justice and fairness will be able to sell their services as judges. Again, firms will arise to do judging. So the executive and judicial functions are fairly easy to see arising.
What of legislative? Well, the law is whatever the protection agencies succeed at enforcing. It is possible they will use democracy, internally, to decide on what laws they will enforce amongst their members. Or perhaps they will simply make up their laws, as a corporation. (Perhaps a vice president will do it in powerpoint.) It does not really matter that much how they get laws, because they are not monopolies. There are many such protection agencies, all competing in the market for protection/enforcement services. That means that if your agency decides to enforce a new law which you disagree with, you can exert consumer choice and immediately punish the agency, by taking your business elsewhere. The practical outcome of this is that agencies will be very conservative about changing their laws.
That's what law will be between two customers of the same agency. But what about customers of different agencies? In the long run, all agencies which might have conflicts will have agreements of some sort with each other to determine which one has "venue" for a particular enforcement action. Why? Consider what happens if they don't. I steal your TV. You complain to your agency. It comes to get me (and/or the TV); I call my agency. My agency has no rule against theft for some reason (it's possible, albeit unlikely) and tells yours to buzz off. Now the agencies can either (a) negotiate sometime (b) do nothing (c) have a war. Wars are very costly. Any two agencies engaging in a war have two big problems. One is, that their own profits drop; they may well go bankrupt. Another is, that if they cause any collateral damage, they will either pay for it or they are likely to have other agencies waiting to hit them when they are weak. Their customers, too, are likely to want nothing of the war, and defect to other agencies. In short, war between agencies is likely to be catastrophic to their market position, and so they will not do it for reasons less than deeply vital ones.
How about the "do nothing" option. Well, if my agency won't defend me, I'll get another. If yours won't defend you, you will get another. Do nothing is not really a viable option.
So, the two agencies will negotiate; they are likely to take their conflict to an arbiter. In fact, all agencies are likely to enter into standing agreements with each other to deal with this problem.
What about different laws? What's to stop an agency that allows the murder of non-customers? Well, in that case, there would be a war; all the other agencies would likely band together and wipe out the transgressor agency if it did not change its policy.
There are plenty of other cases to think about, and some serious problems. The most serious problem, by far, is this: what happens if a protective agency manages to get a monopoly? In that case, it is likely to turn oppressive and ban competitors, which will then allow it to rob and enslave its customers - in short to become a state. What's to stop that? Ultimately, it must be an informed citizenry, who start to get very uncomfortable whenever a protection agency gets too large. Is that likely? I don't know, but I do think it is possible.