Even in spite of these issues, any of the exchanges should be able to pay out withdrawals with a short delay of well under 24 hours, just by aggregating the backlog into one single batch transaction and sending it out using the regular bitcoind software.

If I were operating an honest exchange and had a "spreadsheet" of bitcoin payments I needed to pay out, I would pay them all out in one giant "sendmany" transaction.  Even if the transaction got mutated prior to confirmation, there is a 100% chance the transaction would go through.  I'd repeat the same process daily or several times a day, and announce that only "instant" withdrawals are no longer available, they just have to be done in a batch, by hand, hopefully the same day.

I am guessing that even if the other exchanges must temporarily halt withdrawals, the honest ones will quickly find a way to get withdrawals pushed out with a 0-24 hour delay!

I am pretty critical of MtGox and stopped using them more than a year ago because I just don't trust them.