It may yet be too early to address the "moon base" scenario directly (unless of course you are Newt Gingrich), however, the concept underlying this discussion is not unlike the one the first European settlers in America (among other colonies) struggled with.
There appears to be two libertarian schools of thought on this subject.
The purist camp makes the claim that absolute property ownership does indeed deprive non-owners of their rights to that land, a fundamental resource of life that all have equal rights to. Subsequent transfers of owned land to other parties is permissible and just, even in this purist view of libertarianism, so long as the transactions are voluntary, non-coercive and non-aggressive. The trouble arises in the original transfer of ownership from "no one" to someone. The purist argues that since all people have rights to all land originally, that unclaimed land is not owned by no one, but by everyone.
At time 1, nobody owns anything, and everyone can access any piece of
the world. At time 2, someone has “homesteaded” a piece of the world.
This homesteading is done entirely unilaterally. Everyone else in the
world is not consulted; their consent is not provided. [1]
This means that the original transfer of ownership was not voluntary and therefore unjust. Future transfers then inherit the original injustice. As such, it is only right/moral/ethical to claim the unclaimed land once consent has been gathered from everyone on the planet.
The second school of thought that was supported by the John Locke school of classic liberalism "recognized that absolute ownership of natural resources could deprive liberty, but classified the great amounts of land populated by indigenous peoples as "unsettled", avoiding the issue in theory, if not in practice. [2]" Essentially, they accept the position that unclaimed lands are truly unowned and can be claimed by anyone.
The crux of the difference is that this school of thought contends that the natural resources, while they do exist and everyone has an equal right to them originally, it is only through the labor of man (the owner) that can realize any value from those natural resources. For example, coal has no heating value to you merely by existing. Sitting next to a pile of coal will not keep you warm through the winter without someone acting on the coal to enable it to produce heat; this actor become the owner of the coal through their efforts in producing something of value from the coal. Finally, since no one was doing anything with the resource before the initial owner, no one owned it, no consent was required to claim ownership as in the first school of thought, therefore the initial claim of ownership and all subsequent ones are legitimate.
As to your question about the justification for paying someone an ownership fee to claim the land initially, this would only make sense in the purists vision and the someone would potentially be everyone depending on the terms of the transaction you as the potential owner would have negotiated with all other rightful claimants. The latter view would not expect payment for the initial claim as there would be no one to pay.
