Like basically, my problem might've been something like "different number of inputs being used after subtracting the fee" so possibly same behavior observed with this issue on github:
https://github.com/bitcoin/bitcoin/issues/1570
What I think would help would be options to "take any fee out of the amount being sent" which would remove that problem since the coin selection wouldn't change, and would do exactly what you wanted for the 'send all my coins case'. Also, an option to "round sent amount up, up to X btc", useful when sending to another account of yours, would also tend to reduce fees fairly considerably... but I don't know how UI for that stuff could be done in a non-confusing way.
I'm still helpless to debug this / tired of having no way of knowing what's happening when I get this glitch
... Why is there still no way using RPC / API or the provided bitcoin-qt interface to see what all inputs are being used and what the size is for a transaction before you send it?
We really need "coin control" or at least being able to tell which inputs are being spent and/or what the transaction size is, and we need it like last year
Having more visibility / discoverability for "how much kilobyte size is in a transaction" will likely result in more awareness of what the fee structure is, and what the spending / transaction / usage behavior is doing to the network overall. Bitcoin users will likely tend to create smaller-kb sized transaction to reduce or avoid fees, and in doing so, create less blockchain bloat...
The reason I do wallet sweeps (spending smaller inputs, rolling them together into a larger payment to myself) from time to time... in doing so, it means that I'm getting rid of unspent dust / small inputs so that at a later date I won't need to think about unpredictable transaction size / fees as much (occasionally I've needed to spend most of my wallet, only to realize that so many of the inputs were dust / small, the resulting transaction size ended up resulting in a fee which made me unable to afford sending the amount of bitcoin I thought I had available in my wallet. This is something I prefer to avoid.)