The last few months I've been dabbling in procedurally generated content. My latest project is called Ephemeria, a just-in-time procedurally generated city.
I keep track of a 3 block radius around the player. The good thing is that the whole generation thing is repeatable. If you were to more 3000 miles in a random direction and come back, all the buildings would be the same. We can then keep track of any player- or script-induced alterations and replay them every time a block is re-generated.