After a few years there will be plenty of shelters around, as there's one for each wounded adventurer (at least the shelters you've found. I'm not sure about failed/ignored quests), ones you've made, and sometimes ones made by robbers (again, I don' know if they leave those behind when leaving on their own). I haven't found any outside of quests, though (others have reported finding treasures outside of quest rewards).
For other things, I don't think it would add much, as you'd find a half built cabin long after you've built your own, etc.
One thing at least some people would want to see are Njerp war camps, which are supposed to still exist but be rare, but I've never seen any apart from the ones from the escaping slave starting scenario.