1) let the cost of claim expanding increase with their size. Its really great idea and will not harm newbies.
2) walking over claim is also great idea. It will force people to build fences. Treespasing could simply alow you to open a gate, house, containers but that will leave the scent. This way you will still need to invest large LP amount into trespasing to invade someone really protected land.
3) make claims decay. This could be simple as: after two months of not logging in.
I know this 3 steps will not solve everything and it needs to be tested. But it will move the game somewhere else.
I would like entirelly diferent system, where only things that protects you are locks - on a gate, house, chest. And if you want to protect some resource, you need to build a palisade and lock a gate to it. Palisade could be destroyed but not by mere hands. Or just stay there and watch with a bow. Or have a guard dog. Its realistic, but not newbies friendly.