May be there is no need to NAvmesh all the terrain , may be it is sufficent to navmesh it where there are monsters and in places where NPC will move ?
Unless the problem may arise for followers tough ...
If you look at Tamriel from vanilla Skyrim, half the more remote, cliffy areas don't even have navmesh. As the player, you can go almost anywhere, but a lot of the more obtuse mountain-side stuff has no navmesh. Beth didn't seem to mind, so you should be able to get away with doing the same. (As am I)
Though, I would refrain from blocking the player in. Part of the TES/Bethesda Sandbox feel is being able to go anywhere. I get annoyed when I'm boxed in when it doesn't appear that I should be.
In my mod, the player can go wherever they want within my land. On any mountain, up any cliff. I don't restrain them at all. I simply keep them from swimming off, and there is one quest where I box them into a place. That's it. Keep it open, but don't navmesh the more extreme stuff that players will rarely go on.