How would we know that they haven't just paid someone (with a lot of bitcoins) $20k to sign that message?
Also, it's less likely to be a lie if they do it sooner rather than later.
But in the case of a cryptocurrency exchange the credits and debits should be more or less equal, minus the trading fees. At least, that's how places like Mt. Gox promote themselves.
It may take longer to get your funds, if there is a "run" on the exchange, because of the flood of transactions into the system and the need to reconcile everything, but that would likely be measured in a few hours extra, not days/weeks.