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).
The only practical benefit to using waypoint graphs is where you indeed wish to restrict movement to exact lines rather than areas. Waypoint graphs = infinitesimal points and lines, whereas nav meshes are much the same thing just with (convex) polygonal areas attached which describe a valid space considered to be "this cell's territory
". Either way you are interpolating an AI entity's position from one node to another; the only difference with navmeshes is that you are doing it from one locus of points to another, whereas with waypoint graphs you are doing it from one point to another, and potentially giving due consideration to the edge separating nodes A and B. And of course from a complexity perspective, it's easy to see that waypoint graphs are moderately cheaper to operate.
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.
