This is the exact problem our exchange wallet had, if we sent a withdraw and change inputs would get stuck as unconfirmed and all other withdraws would fail stating "already spent"
The network takes the fee not the exchange, just subtract the estimated for display purposes, we just need a wallet that can resend change inputs without a full resync after each transaction, Hoping this version is the one, because I'm starting to feel like people are pointing at us as the blame
Alternatively, create reasons for people to want to hold the coin and use it, and drop the fancy fee structure that causes the problems. Differentiate it in other ways than making it impossible to trade/use or to make the trade/use prohibitively expensive. With the current model it is imperative to have the code right AND to get exchanges to play along. Exchanges will also have only so much patience before they say %$# this because in the bigger picture fly is atm only a small fraction of the bigger picture that is their business. If coin management insist with the artificial exchange control rules, the most feasible other option is to create your own exchange that only trades this coin and then you can as exchange owner sort out the fees and the superfly wallet with recons in the background. Or then sort out the code before the exchanges throw in the towel.
Sometimes when one gets bogged down in the detail, it helps to take a step back, look at the bigger picture and change the approach. When you take that step back and evaluate the bigger picture it seems there is a conflict between two opposing objectives - on the one hand you dont want the coin to be traded by implementing high fees and on the other hand you want to be able to trade the coin without paying high fees. The problem is that it is very difficult, arguable impossible, to satisfy both objectives at the same time. The current alt-coin system is geared to either one of these extremes - this means to satisfy the one objective you will have to drop the fancy fee structure which will enable trading. To satisfy the other objective you drop the exchanges and in the rare case where someone then want to trade the coin they can match a manual trade pair on BCT through making a post. If you want to meet in the middle then you need to change the code to fit the exchange business model, or get the exchanges to change their business model to fit you or to create your own exchange with your own business model. The first and second options will be the easiest with least effort and the last options will require the most effort and will be a tradeoff between effort, time and investor/exchange patience.