One thing I've been thinking lately is that this should be baked into the process for every unit of work, not just those people expect to be difficult.
Instead of estimating by guessing based on reading the requirements, work on an issue for say an hour or so and then estimate it.
It still wouldn't be perfect, but I think this would catch a lot of cases where, for example, a seemingly simple feature ends up requiring an extensive model change.
It would also do a much better job of shaking out cases where the requirements aren't as clear as you thought when you start trying to code it.
Oh, you'd think so. Then you might be unlucky enough to work with some 'senior programmers' who have been 'doing Agile for years' and are able to convince the manager that a spike that doesn't result in code that will go to production is a waste of time. I never worked out whether that was malice or stupidity.
On projects that are breaking new ground it is even more important to follow XP practices like getting frequent feedback from customers, taking the simplest solution that could possibly work to avoid overengineering before you actually understand the problem, to embrace change because your original understanding of the problem probably isn't right.
There also is plenty of risk involved in cookie-cutter commodity work. Those kinds of projects fail all the time.
Example: "architectural spikes" in eXtreme Programming: http://www.extremeprogramming.org/rules/spike.html