Of all the threads I've read related to this topic, I have yet to see any mention of specifics regarding what type of mod is afflicted by this "navMesh bug". So my first questions are:
1 - Is the mod ESM, ESP, or both?
2 - In what file is the navMesh data stored in?
3 - Is the custom navMesh causing problems located in an interior cell or exterior worldSpace?
4 - Does it alter any Vanilla navMesh (besides linking to it)?
5 - Was it "Finalized"?
6 - Was it auto-gen'd?
1. ESP, in both cases for me.
2. In the .esp file, which is the only plugin file the mod has.
3. Both, but exterior worldspace is far more noticeable as broken.
4. Yes, it's necessary to do so in order to fill areas between where the vanilla mesh ends and your actual cell border is at.
5. Yes, they all were.
6. Only two in Riften and one in Whiterun was.
All the advice you give, it's been followed. This isn't some phantom bug that a bunch of incompetent users are generating by some twisted accident of fate. It's very real, it's well documented, and that you haven't seen it yet just tells me you're EXTREMELY lucky or not testing for it correctly.
Easiest way to see it in action under 1.4.x was to edit/create navmeshes, go somewhere >2 cells away from the edited area, then come back. It was painfully obvious when the bug struck.
Take Open Cities Skyrim for example. All navmeshing in Riften was done properly. Two cells auto-gen'd, the rest done entirely by hand. Proper cover edging and finalization. All connections in place, all door linkage in place. Come to the city. Walk around. Everything appears normal. NPCs going about their business. Guards on patrol. Exit out the north gate, walk up to the nearby bandit fort. Turn around, come back to the city. Whole new ball game.
With patch 1.4, NPCs would be standing around on one of two balconies, unable to navigate anywhere else. Many NPCs would simply appear to have vanished, I never did figure out where they ended up. That was the extent of it though. Even if you fast traveled away and then fast traveled back.
With patch 1.5, this changed for the worse. Now, you visit the city, everything is fine. The trip to the fort and back is also fine. Everyone having a great time. Fast travel out, fast travel back in. CTD. Every time. Without fail. The same has been confirmed across many house mods, village mods, and other efforts which necessitate navmesh editing. You visit once, everything appears just fine. You leave, then try to fast travel back, CTD.