It is worth noting that anarcho-capitalism does not imply anarchy, in the sense of an uncontrolled society without rules or without the enforcement of rules, nor does it imply the lack of governmental forces. Additionally, it is distinct from plain anarchism in that it is perfectly capable of supporting, and indeed may encourage, hierarchical social organizations. Whether or not there's a government is partly a matter of opinion over what counts as a government; what there definitely is not is a single governing organization with legal power over a large state. There may not even be a recognizable unified state under an anarcho-capitalist system (although it, too, is not entirely ruled out).
Protection agencies or enforcement agencies are typically cited as the source of legal authority in anarcho-capitalist systems, but they are not the only options. For a simple extention of that system, legal systems and courts may be provided by other specialized organizations (such as arbitration agencies) for sale to enforcement agencies, or enforcement agencies may be hired to enforce the legal codes of other organizations rather than private individuals. An example of such an organization might be a neighborhood council or homeowners' association. In that case, when purchasing or renting a residence, part of the contract would be membership in the homeowners association and compliance with its rules- one is thus buying a legal system along with a place of residence, and voting in favor of that system with your dollars (or other currency of choice).
When 'voting with your dollars' in that sort of scenario, a 'no' vote doesn't mean that you have to go along with the majority anyway- it means that those laws simply don't apply to you, and you choose a different legal system provider. In this case, you buy a house somewhere else. This provides, first, a profit incentive for any particular legal system provider, be it a housing developer and associated homeowners' association, arbitration agency, or something else altogether, to provide laws that appeal to the broadest range of citizens, and second, a means by which a large number of legal systems can develop to suit any citizen's wants or needs.
Homeowners' associations already perform many of the functions ascribed to traditional governments, and there are private arbitration agencies already in existence that handle out-of-court settlements. Why don't we consider them to be governments? Possibly because they are not sovereign, nor or they empowered by the sovereign state goverment that has power over them. Eliminate the overlying state, however, and the question becomes more blurred. Perhaps under an anarcho-capitalist system homeowners' associations would be considered sovereign microstates, and arbitration agencies the governments of nations without borders.