Sandboxes are trouble. If we build too easily, the world runs out of space. If we destroy too easily everyone is afraid to build. We're not all online at the same time.
Here's my vague, generalized solution:
You can build anywhere. However destruction by players can only happen in contested areas.
Safe areas are safe to build and travel in, hence the name, but are resource-poor, so you cannot hope for much more than a hut and a rusty sword. Yes, the sword could be newly made and still rusty. The local iron is just that bad.
Contested areas would have more resources and better resources. These would be the places to farm. And the places to build if you want to take control. In these places, you can die to anyone, your buildings can be destroyed by anyone.
However safe areas are not places where you can just build away and never worry. Buildings will rot, decay, and be worn away. This would be a percentage of the cost, so that more expensive buildings require more upkeep. They won't fall down in a day, but after a few days of game time they will fall apart until they are ruined and need to be rebuilt. "Game time" is the time you are logged in and time offline if you are leveling skills (such as in EVE). To prevent permanent structures being built by people who never log in, even offline there would be a very slow decay; not so fast that you feel you must log in every day, but so that if someone is inactive for a couple months, they aren't cluttering up the world.
To maintain structures you will need to go out to the contested areas. You can gather and return home, but not without risk.
The overall goal is to allow players to destroy other's buildings without it being a game of waiting until they are offline and then torching everything in the night. You'll instead need to starve them.
Various mechanics would work behind the scenes to keep things running as intended. Resource gathering would be slightly more efficient when the server has more players, so that players are discouraged, though not blocked, from sneaking out when no one is around, while those who operate at peak times are rewarded for the risk of being out when the bandits are too. There would also be an attempt to keep players in more or less the same real life time zone, partly to keep out the dirty foreigners, partly to keep a sense of time (day-night cycle would be related to RL), and partly so that players are taking similar risks.
There will be a risk-reward relationship in this game. Players who want no risk at all could stay in the safe areas and would consequently have pretty awful homes. Players who venture out can get more resources and have nicer properties and items, but will still be limited. Those who take big risks, building directly in contested areas in order to gain control over them* will be able to get more and better resources, but will need them to survive out there. In general it should be balanced so that players will see benefit to building in risky areas but without being so much that everyone feels forced into FFA PvP.
* Control would be physical, not based on game mechanics drawing borders. For example, you might have walls to enclose properties, preventing others from chopping your trees and keeping your herds in place. There could also be traps and magical protections, but nothing that would stand entirely by itself. The goal is still to have players be able to log out without wondering if in the morning everything is gone, but without logging out being a guarantee of safety. One specific mechanic might be self-repairing walls, which can use existing stockpiles to maintain themselves, so that you can log off and survive, but if you don't get back and replenish your stockpile, the walls will be down within a day or so.
Of course everyone loves a good fire, so I will add this bit: even in a safe zone, a building under 10% integrity can be set on fire and will burn down regardless of repairs. Outside safe zones, buildings, if they can be reached (walls will be pretty important), can be set on fire at any integrity percentage, but may be harder to light or will burn slower and can be doused and repaired. So sorry, you don't win just from one good torch toss.
I've not considered how NPCs would fit into this world. Maybe they too would build and gather. I certainly don't want them to be just passively waiting around to be killed or as just a generic malevolent group of bandits.
In closing, I want to let everyone know that I never had a sandbox as a kid. Instead, I had the far superior "dirt place", which was an approximately 5'x12' area next to our house which had no grass in which they used to store coal. It probably gave us all cancer, but coaldirt is a much better structural material than sand, especially with easy access to the hose.
P.S. Thanks to Adam for the inspiration.