My first suggestion was going to be separate type of pavement that doesn't decay on unclaimed terrain, but then thought about it and some troll would probably pave half the world with it unless you'd make it expensive (and then make it prohibitive for the actual purpose it's meant for.)
So my proper suggestion is: make it so that milestones connected to claimed large milestone prevents vine growth on nearby pavement. effect could be restricted to X tiles which would allow like 5 tiles wide road at maximum perhaps?