For Oleg's specific questions, all can be solved by decay. Unmaintained roads,
ships, and buildings slowly crumble into nothingness. For roads, the travel
time slowly increases. For ships, they slow down and risk sinking. For
buildings, they lose fortification and then collapse.
A similar solution can happen to units. Either accelerated aging occurs (so
that in real-world terms a unit dies within a year), or skills left unused
become rustier and less useable.
As to challenges regenerating, there are a couple of things that can happen.
First off, one-shot items such as the Staff of Calyx need to reappear some time
after being used. For computer-controlled beasties, they need to be spawned
every once in a while to keep them in existence.
As to Oleg's an other's suggestions to try to fix things by upping the costs, or
by expanding the land, the problem with these things is that anything that is
at all possible will eventually happen, and happen enough times to "use it up"
, unless it somehow refreshes itself. Decay does this. As to the
ever-expanding land mass, eventually that will run out. You either will have
a bounded-totally explored map, or will have lands so far away that no player
will have time to reach them before their interest wains.