Nav meshes are a qualitative improvement over waypoint graphs, in the same way that A* is a natural progression over Dijkstra's algorithm. In each case, the former has evolved due to the shortcomings of the latter, and is an entirely more useful algorithm for most applications. The shortcoming is, of course, complexity (time and/or space). But I would have to say the tradeoff is small for nav meshes vs. waypoint graphs (i.e. computational complexity may increase, but not by an order of magnitude). For the practical benefits of nav meshes over waypoint graphs, with diagrams, see this blog post. It's clear from this that the only practical benefit to using waypoint graphs is where you actually want restriction of movement to infinitesimal-width lines.
You don't mention any other common types of navigation approaches. That's because the fundamental nature of pathfinding is graph search, and for animals, at the conceptual level, are represented as a sort of graph linking the idea of one place to the idea of another through association, and so on. There do exist other approaches to eliciting AI movement, such as gradient based approaches (eg. Collaborative Diffusion). But they are not nearly as practical/meaningful to us as graphs, under most circumstances, because that is how we humans grok pathfinding. If a mole, a bat, or an amoeba became sentient/intelligent, they might find diffusion gradients more pertinent, for obvious reasons.
As time passes, improvements do come seemingly "for free" (from the individual perspective). That's why a computer you buy today for $X is many times faster than a computer you could buy ten years ago for the same price. The point is, it's not really free -- somebody, somewhere, has put R&D effort into that. Same with algorithms. And that's why older tech mostly falls by the wayside.
