The problem is in the way some companies set deadlines. A bunch of people come up with everything they could possibly want. They pick an insane deadline. People point out that it's impossible. That is, a 0% chance of success. Revisions happen, ending when nobody can prove the the date is impossible. Now they have a 1% chance of success.
A saner approach is the one I first learned from Extreme Programming. Basically, you take every feature that anybody could want and put it on an index card. You put the index cards in order of importance. Do them one at a time, and make sure you have something releasable every week. The first version will be terrible, of course, but eventually the pain of releasing gets smaller than the pain of not releasing.
Using this approach I've happily been very early for deadlines. Sometimes we moved the date up; sometimes we kept the original date and just kept doing less important things. I get to keep coding while product people fight over which cards go where, because I just care about what's at the top of the stack.
I'm at the point now where we don't even talk about deadlines. We put things in order, we do 'em, and we release as soon as possible. We don't do formal estimates; we just keep the cards small (average ~0.5 days, maximum 3 days). That saves a lot of wasted time and stress.