Advanced navigation mesh?
I assume you're needing to handle when the player goes off-mesh for something like... elevated platforms or other unreachable areas.

The key is notifying the AI when the player is no longer on the navigation mesh.  Here's one way to go about it:


Duplicate the nav mesh
Set the physics type to static, ghost, invisible, and give it a unique property
Put a downward ray sensor on the player that sends an onmesh/offmesh message to the AI
Have the AI switch states from path following to [insert desired behavior] depending on the message.


Here's an example where the AI runs straight at the player when you leave the navigation mesh.

The main problem with this method is that your AI could get stuck if the player goes offmesh without having line of sight.

For better results, I imagine you will need a very case-specific Python script that manipulates navmesh.findPath
http://www.blender.org/api/blender_python_api_2_72_1/bge.types.KX_NavMeshObject.html