Obviously the major chunk were always scenes and they are usually also the major contributor to the insecurity of the prediction. E.g. working with people who you don't know, weather, technical problems (broken, missing stuff), stuff that just won't work (animals, certain scenes with actors).
But in the end what always mattered was that there was a time plan for each day and at the end of a day we would know wheter we are A) faster as predicted, B) on time or C) slower than predicted. The next day would then be restructured accordingly by the production and usually you'd be back on time by the end of that.
I was usually spot on with my predictions and we never had any issue with getting the planned stuff done.
With programming the whole thing is harder, because it can be even more unpredictable. But what definitly always helps is when you have a feeling for whether you are too slow, on time or you managed to build a time buffer for future doom.
It's doable, but what people tend to forget is that it's work. If you want an estimate, I need to be able to expend effort providing it. It's an engineering activity that needs organisational support to do it at all well, but often you find an expectation that people will be able to pull an estimate out of a hat just having heard the faintest description of the problem, and there can often be a tacit belief (usually but not entirely from non-technical folks) that not being able to do so makes one incompetent.
You want a narrower range than 0.25–9 months? You'll have to let me think about it. Maybe I can be just as certain that it will be done 1–5 months from now, if I get time to mentally run through the simulation, to borrow the terminology from upthread.
You want a narrower range than 1–5 months? I don't have the information I need to give you that. If you give me a couple of weeks to talk to the right people and start designing/implementing it, the next time we talk, maybe I have gotten the range down to 1–3 months.
I can always give you an honest range, but the more you let me work on it, the narrower it gets.
----
This is of course what's suggested in How To Measure Anything, Rapid Development, and any other text that treats estimation sensibly. An estimation has two components: location and uncertainty. You won't ever get around that, and by quoting a single number you're just setting yourself up for failure.
This is where actual probabilities come in: if you give me 90 % probability ranges (i.e. you think there's a 90 % chance the actual time taken will fall inside the range you give me) that provides me with three extremely powerful tools:
1. First of all, I can use Monte Carlo techniques to combine multiple such estimations in a way that makes sense. This can be useful e.g. to reduce uncertainty of an ensemble of estimations. You can't do that with fuzzy labels because one person's range will be a 50 % estimation and someone else's will be an 80 % one.
2. I can now work these ranges into economic calculations. The expected value of something is the probability times consequence. But it takes a probability.
3. Third, but perhaps even more important: I can now verify whether you're full of shit or not (okay, the nicer technical term is "whether you're well-calibrated or not".) If you keep giving me 90 % ranges, then you can be sure I'm going to collect these and make sure that historically, the actual time taken falls into that range nine out of ten times. If it's not, you are overconfident and can be trained to be less confident.
The last point is the real game changer. A point estimate, or an estimate based on fuzzy labels, cannot ever be verified.
Proper 90 % ranges (or whatever probability range you prefer) can be verified. Suddenly, you can start applying the scientific method to estimation. That's where you'll really take off.
To be honest I still don't really think any of this stuff can be truly verified beyond actually doing it or having a very well understood set of requirements that have been worked against plenty of times before.
About verification I think you're right in a very specific sense: you clearly cannot verify that any single estimation is correct, range or not. However, meteorologists and other people dealing with inherent and impenetrable uncertainty have found out that a historic record of accuracy is as good as verification.