This malleability thing can be handled and I'm sure Bitstamp will fix it (a lot faster than MtGox).

The problem, I suspect, is how change is being handled. As outputs need to be fully spent, you normally produce a transaction with 2 outputs; the desired target address and an address with change that goes back to the exchange itself. However, that change needs to be frozen until the transaction becomes confirmed. Most exchanges probably thought that since it owns the private keys it should be safe to instantly reuse the transaction hash of the change for some other withdrawal, but due to malleability it is not possible to do so.

To get good throughput the coins at an exchange probably needs to be split up in reasonable chunks. It all reminds me of how you implement malloc() in C with free lists for each bucket size. Instead of using a stack (for each free list) you should probably use a round robin strategy.

Anyone being an expert in Bitcoin programming who wants to chime in here?