If you haven't claimed the land it isn't yours. This is literally how this game works.
If you had and unclaimed mining outpost and somebody put a claim on it, then it is now theirs. You never owned that land you were building that wall on.
If building claims is so easy, why didn't you build one? Why not kill the dude who built the claim? Why not Destroy the claim? It sounds to me like you were building this wall before you were really capable of supporting such a thing. This is exactly like all those people that got their houses destroyed before they had yeomanry to claim them. While I can agree that building a claim should have an lp cost, it wouldn't be bad just have the claim start off only claiming the square it is built on. Additionally having a claim have an lp cost wouldn't this guy magically decide to not ruin your day, after all you were being an idiot, it would just make him demand something more than a bunch of wheat seed.
You could also just build the wall around his claim...