A* Returning a Path When There Should Be None

An AI is requesting a path to the player, and is being told he has a direct line path, even though the navmesh does not connect at all. The AI is on a region much higher than the players, and there is no connection between the areas. He keeps attempting to jump off the cliff to reach the player, instead of staying at the edge.

Can you think of any reason this would happen, or any way to prevent it?

EDIT: Changing Max Nearest Node Distance seems to fix this, if I set it to something very low, like 5, but then other AI who are clearly on the same navmesh region as me fail to return a path. This is a pretty big problem, any ideas?