I looked at a number of the failed transactions on skanner before the api facility was stopped and it seems a lot of withdrawal transactions had several inputs, but one of which had zero balance, an initial double-spend. For example. If customers A and B both try to withdraw BTC within a few seconds of each other their payments would share one input address in common with a balance to satisfy only one customer. Whichever gets propagated through the network first has a successful withdrawal, the other is silently ignored, languishing.
That would be better than the reality. My stuck tx is a double spend, and the original was included in a block 10 days ago.
That is right MtGox tried to pay me with "coins" they already paid to a completely different customer over a week ago.
Indeed, what you are describing is worse and seems to rule out db race condition glitches. It is hard to believe that they are having a genuine software problem like this after functioning for nearly 4 years.