I think the main problem in estimating projects is unknown unknowns.

I find that the best approach to solving that is taking a “tracer-bullet” approach. You make an initial end-to-end PoC that explores all the tricky bits of your project.

Making estimates then becomes quite a bit more tractable (though still has its limits and uncertainty, of course). Conversations about where to cut scope will also be easier.

But how long it'll take you to make that PoC? Any idea? :P