Besides, most of the things you mention can be accounted for. If part of your development process involves iterating through the design with the customer every couple of weeks then you build that into your estimates.
Likewise, I always build documentation and code handover support into any serious project rather than acting surprised that customers will want such a thing and expect it to be part of what I'm delivering.
I think we have different intuitions here because it sounds like you're more in a service business than specifically writing software. I agree that a lot of any service business is standardizable, because it's mainly about people and their needs; that has a lot of regularity.
But I don't think the software creation part of a service business is standardizable over the long term. During the first wave of "put smallish businesses on the internet" each web site was custom, hand-rolled software. Early on those schedules were unpredictable, but for a while, it became a known, predictable business.
That business has, in the long term, been basically destroyed. People spotted the regularities and developed common code and tools. What was mainly a problem of software development became a (much smaller) problem of installation and configuration. The competitive advantage for those people now lies not in coding ability, but in customer service and in helping people manage the essential complexity of the domain.
Perhaps you weren't around in the early 2000s when the RAD tools were all the rage.
Perhaps you missed out on the colossal frameworks of the late 2000s when everything was a factory and understanding HTTP was actually a disadvantage as the whole thing would blow up if you actually tried to access the request body.
We went down the road you talk of. It was horrible. Now the pendulum swings to the opposite ends, the light-weight APIs which don't try and abstract away all the details which it turns out mattered a lot as everyone has to do pretty much the same thing, but ever-so-slightly differently. Tiny tools that do one job well.
All you are talking about is writing HTML and doing server config, neither of which are software or programming. When someone in 2000 came to you and said 'I need a website, therefore I need a software programmer to write html and setup a server' they no more needed a programmer back than then they needed one today. Just back then it was developers who knew the markup language and how to configure servers and they weren't about to turn away silly money just because there was not much actual coding involved.
I like crow-flies vs hiking analogy. I'd like to add upon it for so-called "green field" programming as it relates to getting cost predictions correct and understanding programmer time growth in relation to program size. Some parts are linear. Some parts are exponential.
Before I go on talking about "hello-world" space, note that I do architecture and really like architecture, big-picture solutions etc but I try only to solve what is apparent and then iterate on it whenever I notice two pieces tangling. There are excellent wins to be made here, but a working program itself constitutes part of the information necessary to arrive at the final architectural decisions. This is why even on FOSS code, I try not to sweat the architecture on the first pass -- when I do, dead code results. It calls out to me that I have solved something not relevant to the emergent implementation.
Once I've decided what the API might look like, what data structures have to be accessible to what, and what the minimum program states are, I try to stay in what I call "hello world" space. The idea is that the code I'm writing is never doing anything more than one problem at a time, line by line if I don't know exactly what a line does.
This is incredibly efficient because I deliberately break my problem into something testable and well understandable at every step. However, it's impossible to write production code this way. Not only is test feedback, (printlining and frequently more complex testing) not part of the final behavior, but more importantly, the elimination of concurrence of many states, the overlapping of problem workflows in execution sequence, implicitly says that "hello world" space problems are not production code. They have eliminated some functionality or consideration so as to make "hello world" solutions utterly oblivious to concurrent states or processes.
However, two "hello world" problems that need some coordination themselves creates a third "hello world" problem to implement their coordination. The third problem isn't apparent until the first two are explicitly solved. This implies hiking from the article.
Solving "hello world" problems brings more of the problem domain into "hello world" space. The concurrence problem itself will become apparent as a "hello world" problem when it has manifested itself. If there are two states that have been independently implemented but can overlap in execution, there is at least one set of logical statements for dealing with the maximum concurrence of the two states. Growth for N states is exactly an NxN truth table unless some of the states are sparse. In the worst-case, for N "hello world" solutions, one layer of abstraction where all states depend on all other states will result in N^2 logical blocks. While in practice this concurrence is usually much lower, the growth in abstraction is exponential if one is to keep breaking each problem down into an independently writable, testable piece.
So my conclusion is that growth is pretty much linear in proportion to writing "hello world" problems and exponentially proportional how many layers of integration are necessary. Slamming code down ichi-geki style is linear for problems that don't have a potential for overlap and geometric for ones that do. Code that eliminates duplication of routines through logic creates them in implementation, but the payoff is a net gain in many ways, so of course it still makes sense to do it.
As for making predictions, while running my internal monte-carlo, the concurrence of states has a higher influence on the outcome sometimes than the raw code size I expect to come out in the end. Linear and exponential growth occur in different areas. Recognizing that each integration incurs smaller linear component, and that each abstraction layer involves N integrations of solutions, I think it's pretty achievable to have a damned good estimate. The exception is if scope -must- creep and this is only determined in the middle of a project. Scope creep gets paid. Bad estimations do not. Usually scope creep is itself revealed when a new facet of the problem comes up, one which represents a competitive opportunity, which the client is happy to pay for.
Saying that no estimate should ever be good is like saying programmers should make gigantic mistakes. This is only possible when working on W-2, and only when the company won't die. End of discussion. Independents have to get it right. Any thoughts to the contrary will soon land an independent programmer back in W-2. The fact is that clients like predictable cost, and programmers who can deliver it can ask for more because they don't have to start squirming around in client meetings later and making justifications that are inevitably open to self-serving padding and other temptations. Be brave and keep scope, or go W-2.
The big unknown - and the highest risk - was managing integration between external systems, or doing complex integration between internal systems. Anything that might benefit from aspect-oriented programming, like access control lists, or a more elaborate front-controller, or universal exports in json format, or a new paradigm like AJAX, would be difficult to estimate.
That fits your breakdown of projects into linear parts, and exponential parts.
Anyway, my estimates were good, but my business management was not - I was always in learning mode because I never studied business and had no experience. So I went W-2 and went into a different field because an opportunity to learn politics emerged. What's interesting is that successful political campaigns are entirely about estimating and budgeting, in real time more or less - you spend money and see results day by day, or after a couple weeks. It's driven by statistics (and messaging). I just watch from the sidelines, and don't do politics, but I think we could learn something from it. It's more like agile XP than waterfall.
The Obama campaign was XP, by necessity. The Healthcare.gov website thought it was waterfall... again by necessity.
That a project is estimatable has to mean that novelty is low and predictability is high. But low novelty is a sign of duplication, which should be factored out into things like libraries, frameworks, and self-service tools. High predictability is either a sign of duplication or it's a sign that people have basically agreed not to learn anything during a project. If you are shipping early and often and study users and metrics as you go, then you will always learn things that affect the plan. Which means that the schedule isn't predictable even in theory.