[KineticLensman]

Lots of great answers here - but something I wanted to focus on is doing a risk analysis alongside the estimates. Places where I have worked have generated corporate estimates for clients (usually in a competitive bidding situation). One of the sign-off decision points business enforces on the bid teams is to check that they have considered risks to the project, possible impacts in terms of time and cost (usually related), and a risk budget (e.g. for extra days for rework) which depends on the magnitude and probability of the risks. Risks are usually expected to be higher if the work involves any sort of novelty. If risks don't manifest, the business makes more profit, but if they do the PM has a basic safety reserve. The need to keep estimates competitive generally creates pressure to force the risk budget down, but the fact that the process is subject to business scrutiny and independent internal review can lead to mature debate about the issues.

The key to this process working is to have a tech assurance function that is independent of the bid team and their management, and that the overall company accepts the process. The assurer can say to the business "I think you are pricing this too low for the risks involved" but it is specifically not the reviewer's call as to whether the bid is submitted or not, so management can still submit the estimate if they want to. But, if things subsequently go south, the blame isn't immediately passed to the bid team or the delivery team.

Alternatively, generate an estimate, round it up to the next order of magnitude, and double it.