Waterfall as it was done in early 2000s was mostly a high level plan and smaller unofficial iterations on the ground. We knew we need to test, and sometimes partially release stuff in advance to have an idea of what's actually working and what's half baked.
The same way successful agile projects are almost always done with unofficial rough planning and dependency graphing checked ahead, and smaller iterarion following the big picture from there.
On both methodologies, religiously adhering to the mantra is suicidal, and I don't see agile being significantly better except if all you care about it getting paid iteratively -- which is a noble goal for a consultant.
Perhaps the point that bears reiterating is very few shops actually followed hard line waterfall planning (nor agile, for that matter).
Waterfall is suited for projects where the outcome is known (e.g., guidance software for fancy new jet, embedded software, etc.) where establishing a deadline is necessary and possible because the desired feature set is fixed (at least in theory) and changes are locked behind a (likely multi-year) requirements and design process with contacts and lawyers.
Agile is better suited for exploration of a product space or implementation of projects where agility (surprise, surprise) to changing/unknown client needs is paramount. Clients don't know what they want till they see what they don't want, so agile is great for that type of build. The web-facing world loves agile, because the "end" goal is usually, "make money so we can hire more developers to build more website [whatever that means] to make more money to hire more developers...".
There are means of mitigating bad estimation (e.g., Spolsky's "Painless Software Schedules" and particularly "Evidence-Based Scheduling".), but you can't account for a 50 hour feature added 19 weeks into a project. Agile (acknowledging the broadness of that category) alone doesn't do anything to mitigate either bad estimation or surprise features, it simply trades "known deadline, fixed features" for "unknown deadline, flexible features".
I'm unconvinced. If new features of unknown complexity are getting added to your product backlog with the expectation that estimations are done against them and not that exploratory work is planned and undertaken instead, that's a problem with the culture and not with the process.
Scrum in particular (according to Coplien et al. at least) is meant to handle prioritization of work as a conversation between the people who want stuff built and the people actually doing the work to get stuff built. The only thing it recommends—not even prescribes—as it relates to estimation uncertainty is embracing the framework to chart a new course more easily when the facts change.
A big pattern that is prescribed (though perhaps only implicitly via reiterating that the product backlog is strictly in delivery order when work starts) is that the product backlog is append-only when you don't want to trigger more planning and, as a direct consequence, draw up a new refined product backlog for everyone to work from. If you need to reorder your product backlog items to add something in the middle, that's a signal that the facts have changed, and the plan needs to be redone. That isn't prima facie all that different from a more traditional project management method.
Agile only aims to make planning suck a little less to change by baking certain touch-points into the process so that someone can pull the proverbial andon cord unceremoniously.
> Agile is better suited for exploration of a product space
More apropos this, if you've ever heard of a spike solution, that's agile's attempt at controlling for uncertainty when it isn't exactly clear how to do something or how long something will take. It necessarily triggers additional planning, and the product backlog item for it is a clear display of the uncertainty inherent in delivering that helps determine where in the ordering that work should fall.
Likewise, if you generally know what the roadmap looks like and have confidence that it won't change, the uncertainty is still in the humans doing the work. I've always put vacations and bereavements and on call shifts and other kinds of fixed-date "generally not available for product work" things into the product backlog, and having that visible to everyone with stake in the work is always valuable.
You could say "requirements are satisfied", is the threshold but those always change on a project. You need to predict what you need in the future. No one is good at that, but the fact that some may be lucky does not imply that it's possible. Doing it right in a schedule based environment means contract renegotiation. This could be expensive and many times its easier for the customer to bypass management and convince the engineers to take on more scope for free. This happens all the time, project managers need to be vigilant! But vigilance does not build value, it just creates avenues for conflict.
Regardless of what your methodology is, every successful project will become a "unknown deadline, flexible features" product at some point in its life-cycle. Why are we bifurcating that stage at an arbitrary point based on faulty assumptions made months and years in the past? What agile does is it moves the arbitrary bifurcation point to t=0 and avoids classes of zero-sum customer-management-worker conflicts.
Agile became adopted because waterfall is suited for construction projects or factory floors not software development. It accounts for the fact that software developers are very poor estimators (even the best software devs) determining how long things take to build or implement.