Large, 95% static, randomized terrain chunks

I am sort of lost to which pathfinding graph methodology to use (grid, recast, etc), so I am looking for help to prevent me from continuously spending time prototyping different solutions.

Here is the basic concept:

I will have about 100 individual 1km x 1km (might change it to 2km x 2km). Each terrain has already been created, and is is 95% static (tree’s and actual terrain do not change), however the final 5% could change with the addition of structures on the terrain, at run time.

At runtime, at start of new game, I randomly stich together a starting map from the 100 terrains. The start is 9 terrains, with the character in the middle. New random (from the 100) terrain chunks are stitched depending on which way the character navigates (so procedural). I only need pathfinding on AI’s, and only AI’s within 750m of the character (any AI beyond that distance is faked).

I have looked at procedual however it seems that the 750m line of sight might be a performance issue.

So do I go Grid, Recast, do I load saved graphs, etc. Any pathfinding help/direction would be much appreciated.

I have PRO version.