Navmesh agent passing through obstacles (path goes under navmesh)

Hello guys, I have this terrain ( 2000 x 2000) in which i have a number of navmesh agents moving on the terrain. In some cases some of the navmesh agents get stuck because of invalid paths (10% of the time, at first i thought the paths are passing through obstacles, and they do, but the main reason they pass is that the path is made under the navmesh? [or the gizmo only shows it that way?] )
Can this be caused by the size of the terrain? - I am using Unity 5.4.0f3

Did you fix it now?
If not, could you show the Nav Mesh from above?

Are the agents going after waypoints? Did you check every waypoint is accessible/not blocked? Agents tend to have weird behavior when they’re not.

I also have bugs with Nav Mesh, very useful but on simple geometrical settings…