The answer there would depend on how you define "state." Is the decentralized polity envisioned by anarchists just a very sophisticated state? For certain definitions of the word state, yes.
I think most libertarians use
Weber's definition. Although per wikipedia's article on the
state, technically, many large complex societies have not been states by Weber's definition. For example, in medieval Europe, legislative and judicial functions were shared with the Church and executive functions were shared with nobles. In fact, not even most present-day states fully match Weber's description.
Take for example the WTO, which has pierced the wall of sovereignty for dozens of countries on matters of trade -- yet, since the WTO has powers of enforcement and coercion it could be construed as a government. It certainly seems to fill that role.
I think libertarians are drawn towards Weber's definition because they oppose the monopoly aspect. More specifically, while you can make an argument for laws against a
particular offense needing an enforcer, and you can even make an argument that over some optimal area a natural monopoly might exist, what you can't justify is that said natural monopoly is identical in scope regardless of the offense in question. That is one of the crucial failings of the nation-state (especially ones lacking in federalism) -- that the optimal enforcement areas for different crimes are bundled together under a single organization.
Furthermore, regardless of internal organization, the boundary between two states can and will cut through the optimal enforcement area for certain offenses. In addition, the boundaries between jurisdictions do not adjust in a dynamic fashion primarily because the principle of free exit and entry from polities has only been applied to the entire package deal provided by particular states rather than piecemeal to the components of the package.
As you can see, the range of potential enforcement systems approaches infinity. The only systems that we can rule out as unstable are:
1) Conditions where groups are fighting over who will enforce a particular rule, and especially where groups are attempting to be monopoly enforcers.
2) Conditions where persons exempt themselves from enforcement of any kind.
Note, that both of the above conditions occur all the time even today. Having a Weberian state does not eliminate these conditions, as different bureaus will fight over who gets to regulate a particular activity and insiders will secure for themselves exceptions to the rules.