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.
This is a practical proposal, good job.
From what I can understand this has also the advantage of allowing the previous withdrawal mechanism to be immediately reinstated: a separate program could inspecting only the pool of missing transactions.
I'm assuming here that only a small part of the transactions go missing, so the rest would go through just fine.
Is there an a way to estimate the number of transactions Mtgox produced and the number of those that went missing?