Current withdrawal process (simplified based on the information that we know of)
1.   Record the bitcoin withdrawal request (R0) submitted by its customer via mtgox.com
2.   Identify an address (A1) in Goxs hot wallet that has sufficient amount of bitcoins
3.   Using the hot wallets private key to generate/sign a send transaction(TX1) for the requested bitcoin amount and receiving address (A2)
4.   Record TX1 ID and link it to the R0 ID in their database so the customer can see it in the Account History page
5.   Verify TX1 ID in the public Blockchain after certain amount of time and update the database if it's been confirmed
6.   Otherwise log the TX1 ID in its failed transaction file if it has been rejected by the Bitcoin network
7.   AUTOMATICALLY go back to step 2 if TX1 ID is found in their failed transaction log file (I HOPE this step was NOT AUTOMATED, otherwise they could have been a real victim of some of their malicious users).

Proposed change/solution (No change to the current Bitcoin protocol is necessary)
1.   Same as step 1 above
2.   Create a new Bitcoin address (A0) and keep it private to themselves
3.   Identify an address (A1) in its hot wallet that has sufficient amount of bitcoins
4.   Send the requested amount of bitcoins from A1 to A0 using a new transaction TX0. Record both A0 and TX0 ID after its confirmation (don't expect any problem here)
5.   Send the requested amount of bitcoins from A0 to A2 (requestors receiving address) using another new transaction TX2. Record TX2 ID.
6.   Once TX2 ID is confirmed in the public Blockchain, update the transaction status in the Web database for R0 so that user can see/check that TX2 is the transaction that credited their wallet address.
7.   In case that TX2 has been rejected but A0 is empty, get the last transaction ID (TX3) associated with A0 (and A2), then update TX3 ID in the web database for R0 so the user can see/check TX3 is the transaction that credited their wallet address.
8.   Never automatically retry failed withdrawal transactions.