When a pass of CreateTransaction fails to select enough bitcoin to meet the nFeeNeeded the next pass through may select a far smaller collection of inputs.  Currently it will continue to use the old fee amount based on the larger set of inputs, which can cause a non-trivial over-payment.

This may be the cause of the behavior reported here: https://www.reddit.com/r/Bitcoin/comments/5ltw5n/bitcoin_core_v0131_sends_enormously_high_fee/

Long ago fixing this was tricky due to a catch-22 between signing the transaction and knowing how much fee was required.  But after #9465 the whole algorithm will run using a dummy signature, so when there is already a change output fixing up the fee after finding a sufficient transaction should be a matter of a ~2 line change.

{
    
    
    ReacceptWalletTransactions();
    
    if (!CWallet::fFlushThreadRunning.exchange(true)) {
        threadGroup.create_thread(ThreadFlushWalletDB);
    }
}
bool CWallet::ParameterInteraction()
{
    if (GetBoolArg("-disablewallet", DEFAULT_DISABLE_WALLET))
        return true;
    if (GetBoolArg("-blocksonly", DEFAULT_BLOCKSONLY) && SoftSetBoolArg("-walletbroadcast", false)) {
        LogPrintf("%s: parameter interaction: -blocksonly=1 -> setting -walletbroadcast=0\n", __func__);
    }
    if (GetBoolArg("-salvagewallet", false) && SoftSetBoolArg("-rescan", true)) {
        
        LogPrintf("%s: parameter interaction: -salvagewallet=1 -> setting -rescan=1\n", __func__);
    }
    
    if (GetBoolArg("-zapwallettxes", false) && SoftSetBoolArg("-rescan", true)) {
        LogPrintf("%s: parameter interaction: -zapwallettxes=<mode> -> setting -rescan=1\n", __func__);
    }
    if (GetBoolArg("-sysperms", false))
        return InitError("-sysperms is not allowed in combination with enabled wallet functionality");
    if (GetArg("-prune", 0) && GetBoolArg("-rescan", false))
        return InitError(_("Rescans are not possible in pruned mode. You will need to use -reindex which will download the whole blockchain again."));
    if (::minRelayTxFee.GetFeePerK() > HIGH_TX_FEE_PER_KB)