I'm not going to answer all your questions because I don't know a whole lot about navigation meshes. But your estimates of the complexity of algorithms are kind of high. Just about any space-partitioning method will bring down figuring out which polygon you are on to O(log(n)). Generating the graph structure can be done offline and its complexity doesn't matter a whole lot, but I still doubt it's worse than O(n*log(n)) if you use a space-partitioning method.
I did not knew about space partitioning method. Isn't this comes in hierarchical path finding? The game on which I am working on is not that complex or big. There are simple static walls and obstacles to be placed in the level. Maybe, I did exaggerated on algorithmic complexities of the problem but I did so with my understanding of the problem's solution.