You gave Murray Rothbard’s definition of the state: An institution “which possesses one or both (almost always both) of the following properties: (1) it acquires its income by the physical coercion known as “taxation”; and (2) it asserts and usually obtains a coerced monopoly of the provision of defense service (police and courts) over a given territorial area. An institution not possessing either of these properties is not and cannot be, in accordance with my definition, a state.”
You wrote: It seems a Homeowners Association established by some kind of perpetual contract (such as a restrictive covenant) that includes some means to collect revenue to pay for common expenses, which also includes the provision of a private contracted security force, could easily meet these criteria.
From the libertarian perspective, the NAP is the foundational principle of any legal order. Within the parameters of the NAP, individuals are free to contract in any way they wish; not to be able to do so would be a limitation on their freedom. One way to exercise their freedom to contract would be to subscribe to a Homeowner’s Association which embodied in its articles a set of restrictive covenants (RCs). It would, of course, be extremely foolish to subscribe to any contract in which the possibility of exiting from it at some stage was not envisaged and the conditions of such an exit set accordingly.
So, take the case of the Homeowner’s Association you mention. Let us suppose that under a RC you are not entitled to keep pets in your home. Now suppose you discover you have an irresistible desire to have a dog – what do you do? Well, you could sublimate this desire and continue to live where you reside or you could go somewhere else. This is the point at which the wisdom of having exit conditions comes in. You should have considered the possibility that no one (at least in the short term) is willing to purchase your home under the existing set of RCs so that would place you in a difficult financial situation. One obvious way to deal with such an eventuality is that the contracts would include a provision that the HOA would purchase your home from you at a pre-agreed price or some other financial mechanism.
You ask: Is there a qualitative difference between such an HOA and a State?
Yes. Using MR’s definition of the state, a HOA either does not acquire its revenue by physical coercion or, if it can do so, its right to use physical coercion to collect revenue results from a contract and so does not violate the NAP. So too, there is no necessity whatsoever that a HOA would have to be a monopoly provider of defence services in respect of the properties under the remit of the HOA. Therefore, HOAs are not states.
You wrote: It would seem that an anarchist society would need to avoid certain kinds of contracts to avoid gradually taking on the characteristics of a State.
Well, yes. Any form of contract that ceded to others a right to help themselves to whatever portion of your income and/or property they deem suitable, from which you cannot exit and which tracks you wherever you go. According to contractarian political philosophers, we are deemed to have entered such contracts tacitly or implicitly. We can’t enter a contract to buy a TV implicitly but we can, it seems, enter a contract implicitly that affects our fundamental rights and freedoms!
You wrote: And these HOA contracts would fall into that category.
The one you described above might do so. Don’t enter such a contract! People sometimes make foolish decisions. There is no mechanism known to man that can rule out completely the operation of human stupidity.