Since we use Agile methods (Scrum, specifically) it takes us about an hour longer than it takes the users to prioritize.
More time doesn't lead to more accuracy.
The hard part, then, is getting the users to prioritize. We hear this discussion all the time "if the whole thing isn't completed on time, it's all worthless." "Except for the XYZZY component, which does have some value." That argument can go on for hours until it's resolved that XYZZY should be first.
Generally, we try to create 4-week sprints. The first few are complicated because there's always something new. After the first two (or three) we seem to set a steady pace.
Each use case has a relatively simple, subjective valuation of how the effort it will take to finish it. Anything over one full sprint in duration has to be decomposed. Most times a few use cases are bundled into a single sprint.
The are formal ways of scoring each use case to better handle the cost and schedule issues. We don't use them because the extra effort doesn't help.
After the first two sprints,
There's new and different functionality,
The priorities have all changed,
The details of each use case have been dramatically revised.
What does "accuracy" mean when the thing you're trying to estimate changes at the end of each sprint?
One lesson learned. Parts of my company spend a long time fully defining exactly what will be delivered, and then measuring that they are delivering precisely what they want.
Customers notice this, and one said we "spend a lot of time delivering what the contract says, but it isn't what we needed."
The problem with firm up-front estimates is that they take on a life of their own. The more you "invest" in the estimating, the more the estimates seem to be a useful deliverable. They aren't useful because they're generally totally wrong. They're based on up-front assumptions that are totally wrong.
It's a bad policy to invest more time in estimating. The "accurate" answers aren't more accurate, but they are more treasured by every layer of management. As you and the customer learn, you invalidate numerous assumptions and you absolutely must re-estimate constantly.
Don't do it up front. If your contract requires you to do it up front, then make sure you have a change control provision and tell the customer that you absolutely will make changes as you go forward. As both you and the customer learn, you both must make changes.