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.

{
    int ret = 0;
    int64_t nNow = GetTime();
    const CChainParams& chainParams = Params();
    CBlockIndex* pindex = pindexStart;
    {
        LOCK2(cs_main, cs_wallet);
        
        
        while (pindex && nTimeFirstKey && (pindex->GetBlockTime() < (nTimeFirstKey - 7200)))
            pindex = chainActive.Next(pindex);
        ShowProgress(_("Rescanning..."), 0); 
        double dProgressStart = Checkpoints::GuessVerificationProgress(chainParams.Checkpoints(), pindex, false);
        double dProgressTip = Checkpoints::GuessVerificationProgress(chainParams.Checkpoints(), chainActive.Tip(), false);
        while (pindex)
        {
            if (pindex->nHeight % 100 == 0 && dProgressTip - dProgressStart > 0.0)
                ShowProgress(_("Rescanning..."), std::max(1, std::min(99, (int)((Checkpoints::GuessVerificationProgress(chainParams.Checkpoints(), pindex, false) - dProgressStart) / (dProgressTip - dProgressStart) * 100))));
            CBlock block;
            ReadBlockFromDisk(block, pindex, Params().GetConsensus());
            int posInBlock;
            for (posInBlock = 0; posInBlock < (int)block.vtx.size(); posInBlock++)
            {
                if (AddToWalletIfInvolvingMe(*block.vtx[posInBlock], pindex, posInBlock, fUpdate))
                    ret++;
            }