I know you're going to find this objectionable, and I don't think I'll ever be able to convince you it isn't, so I leave you with this: If and when private security agencies start providing a genuine alternative to governments, I'll rethink my position.
Let me see if I get this right:
You think "I own it because I was the first one there, and marked it" (however that marking gets done) is
not legitimate, but "I own it because I killed the fuckers who lived there, and anyone else who tried to move in" is?
That's what it's going to come down to in the end. Your hypothetical AnCap community can have homesteading, if and only if your security agencies are willing and able to impose it on everyone who has a different idea of land ownership. Any philosophical justification you can give for taking land is bound to be questioned by people with different values. Violence is just about the only thing that's beyond question.
We live in a world where the rewards of killing are great, and often the only practical way to stop a killer is to kill them. I'm not saying the greatest killers SHOULD have the ability to impose their will on other people, I am stating the simple fact that they DO have it.
There is a world of difference, both philosophical and practical, between imposing that definition of ownership on someone and defending that definition of ownership from someone.
Let's posit two groups, one of which recognizes ownership of land, and one which does not. On the one side, we have a group of AnCaps, who recognize sticky ownership of property, and homesteading. On the other, we have a group of anarcho-communists, who do not recognize homesteading as a valid way to own land, or indeed owning land at all. they only recognize use. Let us further assume that the AnCaps have the best weapons and training, and can, if they choose, impose their order on anyone they come up against.
Our first scenario has the communists occupying a plot of land. Amongst themselves, they peaceably share the land, and all use it as needed. The group of AnCaps comes along, sees that they have already occupied and altered the land they are using, and moves along, looking for un-homesteaded land.
Our second scenario has the AnCaps occupying a plot of land. There is one plot which is owned, but kept pristine for reasons left to the owner. The communists come along, and seeing this unused plot of land, decide to set up shop. The owner of that land, assuming he didn't keep it unused for the purpose of dirty commies setting up a campground, will desire them off the land. So, off they go, by force if necessary.
Now, let's posit a third scenario, where a group of geo-libertarians come along and start telling the AnCaps that because they own land, they owe the geo-libertarians a land tax. They would correctly view this as an attempt to steal from them, and defend their property, with force if necessary.
While we're at it, Let's posit that a group of AnCaps come across a group of geo-libertarians who have already set up shop on a piece of land. They have all agreed that in order to fund their community, they should all pay a land tax to whatever agency they have deemed rightful to collect it. Since the situation is voluntary, the AnCaps shrug, and move along, looking for less crazy neighbors.
You don't impose it on anyone who has a different idea of land ownership, only on those who try to impose that different idea of land ownership upon you.