From my experience, making large scale changes to the exterior Tamriel navmeshes is tricky. As a general rule, you don't want to delete the existing navmeshes as this will lead to the sorts of problems you've described. Instead, you either want alter the existing navmeshes to suit the changes you're making, or I've heard of some people moving the entire navmesh of a cell well below the ground level and creating a new navmesh in it's place, at ground level. Either way, the original navmesh remains. You can basically delete all but one triangle from the existing navmesh, and then just start to recreate it to suit your needs. Because you're starting from that one original triangle, the CK won't change the ID of the navmesh which I believe is the important part. I'm no expert on this but just thought I'd pass on what I've picked up along the way. Good luck!