Rather than being a static trees/rocks, how about turn them into wandering treants or a wisp or whatever creature you devs want. .
And to prevent them being walled off and claimed, let them pass through walls and if they detect a claim nearby, they would wander away from it.