"What if, in a society run on voluntary principles, corporations were to become warlords by enslaving the entire population in a military style dictatorship? And... how do we protect ourselves against other governments looking upon our purple mountains and fruited plains with greedy watering mouths?"
The simple answer is that people in a voluntary society would prepare for such attempts and would set up mechanisms to prevent this. I obviously can't predict exactly what mechanisms people would choose, but here are some ideas:
(a) Many, if not all, private security organizations (PSOs) and dispute resolution organizations (DROs) would see value in having a plan to work with other PSOs to defend a large region against attack from other "Nations". Their customers might even demand they contractually promise this kind of service. Similarly, they would join to take down any PSO who decided to go rogue and become a warlord.
(b) A mobile phone app that alerts a large number of people to an invasion so that defense can be as speedy as possible (penalties for false alarms would also be recommended).
(c) DROs and PSOs would be bound by large bonds to be forfeited if their Voluntaryist code of conduct is breached.
(d) Internet and other media to investigate any entities capable of amassing an army, and to report on any who are unwilling to be completely transparent. Of course, there are an infinite number of possible ways which the problem of security can be solved. In the absence of government, it would be in every person's immediate interest to seek out flaws in the security provision system and fix them. People are creative when faced with challenges, and when large groups of people put their mind to a task, they can be completely unstoppable. Viewed in this light, the protection offered by government defense forces no longer seems like the firewall it was commonly thought to be.
The following is paraphrased from a bigger article here:
"But if I were the even halfway apparent leader in the dominant free state with its own private military-security apparatus in such a world... any small/weak/vulnerable states around our border would soon find themselves to be the proud recipients of: MILITARY ANNEXATION. After that I might begin to stretch the common conception of small/weak/vulnerable... People are selfish, uncaring, gain driven motherfuckers as much or more so as we are also empathic, feeling, beneficent caregivers."
You have described not an Anarchism but a State. Illegitimate use of terms. Warlords are micro states in contention for macro-state control. So if you are talking about an Anarchic society that would result in the strong party taking over, you are arguing from a non Anarchic example. But for sake of argument, let's go with the flow for now and address the question head on:
(a) If you are arguing that the defending border peoples are Anarchic, yeah, they might lose, assuming they do not themselves have their own PSO (Private Security Organization) and/or peaceful relationships with neighboring PSOs (sidetrack discussion). Or it might take a hundred years of trying. See 400 years of Irish resistance to British takeover. Defenders will typically have a huge advantage for many reasons, including: more at stake, supplies, and knowledge of the territory. Finally, it's important to consider that without government-forced tariffs and other trade barriers, business relationships between local and foreign companies will flourish, meaning potential foreign invaders will think twice about harming those relationships. More on this below.
(b) The law of comparative advantage. It's actually in the interest of all for even the strong to cooperate with the weak, because *control is expensive* and more so than markets. The Vikings were in the process of shifting from raiders to traders around the time of stiff British resistance, partly because of that resistance, and partly because *they got more prosperity out of settling and trading*.
(c) [tongue in cheek here] Your theory explains why the US annexed Canada as soon as it was able to... oh wait. There isn't a single person in the US or Canada who imagines that Canada could withstand a military annexation. And yet, since 1812, when Canada maybe could defend against US aggression, it hasn't been there. *The trading relationship is so intertwined now that annexation would vastly disrupt the US economy, let alone Canada*. Private agencies own the assets at their disposal, whereas politicians (especially in democracies) merely exercise temporary control over the State's military equipment. In the 1860s, would large scale combat have broken out on anywhere near the same scale if, instead of the two factions controlling hundreds of thousands of conscripts, all military commanders had to hire voluntary mercenaries and pay them a market wage for their services?
(d) Social pressure, shame, and approval drive hierarchical societies and Anarchic ones. Hierarchical ones find this dangerous, because the few rule over the many only by the acquiescence of the many. If the few ever sufficiently displease the many, bad things happen. What that level of disapproval is depends on the specific cultural and historical data of the case, but this is why hierarchies try to control information so thoroughly. In a modern society, more than ever, what with peer to peer communication and mass many-to-many channels, it is much harder to keep people from knowing things. Social pressure had huge impacts on American imperialism. Didn't end it, but it moderated it. It's what gave Gorbachev the ability to dismantle the Soviet State. You can't discount the extent of this pressure. A modern statelet (or private group or warlord) attacking its neighbors is going to have to sell that more intensely than before, because information is harder to control. The more such a warlord overrides the social approval, the less strong his economic and material support for this annexation effort, the more other neighbors will start banding together in mutual defense agreements, the more groups worried will bribe away support, the more he will have to deal with domestic disturbance, etc. Humans don't like bullies. This is why people can hate America while still liking Americans.
I highly recommend you check out the two short animations on this page that describe exactly this kind of thing: