Ok here is what I've done in the past:
1) I'd use a series of nodes to create a lattice, instead of a mesh. The reason for this, is that you can massage the data, as well as having a small data set, hence faster.
2) When you click you're AI, it needs an entrance an an exit node. You can run various distance checks to get the node. (Manhattan,Non Square Dist, or Squared Dist) Also you'll need to do a physical probe against the collision geometry and reject closest distance, if say, a node is behind a wall or some other obstacle. Doing this in a game can become expensive on the CPU side of things.
The best solution for this is to store the closets waypoint data in a bucket system. Either linear buckets, quad or octtree. The smaller the buckets, the better the closest data solutions will be. I'd generate this data off-line in a pre-compile step. That way you can use as complex heuristics as necessary.