I find that I often don't have a good feel for how long something is going to take until I'm about 1/4 the way through the project. If I absolutely had to produce accurate, high-confidence estimates, I would just do 1/4 of the work first, then estimate the rest.
As to why estimating is so hard, here's how I like to think about it. Tasks form a tree: each project has a number of steps, each of which itself breaks down into sub-steps, and so on. We tend to estimate by thinking about the tasks near the root of the tree; but the actual time required is proportional to the number of leaves -- tasks we can implement without further breakdown. Without planning the entire project out in detail it's hard to know what that number is. But to plan to that level of detail requires making many design decisions; and researching and making those decisions is much of the work of the project.
The bottom line is, good estimates are expensive to produce, and my experience aligns with yours: it's rarely worth the trouble.
What I think people try to get from estimates is a sense of control. But I think there are better ways of giving people not just a sense of control, but actual control.
Too many project processes treat estimates as commitments with no backup plan when they (inevitably) go awry. I think a better approach would be to design your system around the idea that all estimates are suspect until proven otherwise, which of course leads to iterative approaches etc.
However, you can't run a business without any idea when anything will ship. Estimation is still, in my view, a very necessary step, so long as there is significant incentive to get it right rather than get it fast, AND the business is receptive to a little ambiguity through the project life cycle. This is a very difficult balance to strike.
In my experience you can have certainty in project scope or time, but not both.
I agree you can't run a business without any idea when anything will ship. But to get a good idea when things will ship, you don't need estimates.
For example, in the Lean world there's something I've heard called "Disneyland scheduling". You break the project down into lumps. You maintain a queue of the lumps. You measure the average time from position X in the queue to being released.
Now you have a reasonable early warning system for when things will ship. Which is generally much better than what people have with most projects, which is a fantasy date.
One of my big aha moments about estimation was a bit in McConnell's Rapid Development. He pointed out that most estimates get made with executives pressuring for short numbers. When you iterate a few times with that, you end up with the smallest number that developers can't absolutely prove is impossible.
If you draw out a bell curve of probable completion dates, this is basically the same as picking one far to the left, so you have a 95-99% chance of being late. But somehow, executives are still surprised when their totally biased approach yields the numbers they liked, not the numbers they needed. All the estimation effort was pure waste; our time would have been just as well spent making cotton-candy raincoats.
I now have done a few projects with little to no estimation, and it has gone much better. I have a hard time now seeing why we ever bothered.