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.

int64_t nNextResend;
    int64_t nLastResend;
    bool fBroadcastTransactions;
    /**
     * Used to keep track of spent outpoints, and
     * detect and report conflicts (double-spends or
     * mutated transactions where the mutant gets mined).
     */
    typedef std::multimap<COutPoint, uint256> TxSpends;
    TxSpends mapTxSpends;
    void AddToSpends(const COutPoint& outpoint, const uint256& wtxid);
    void AddToSpends(const uint256& wtxid);
    
    void MarkConflicted(const uint256& hashBlock, const uint256& hashTx);
    void SyncMetaData(std::pair<TxSpends::iterator, TxSpends::iterator>);
    
    CHDChain hdChain;
    bool fFileBacked;
    std::set<int64_t> setKeyPool;
public:
    /*
     * Main wallet lock.
     * This lock protects all the fields added by CWallet
     *   except for:
     *      fFileBacked (immutable after instantiation)
     *      strWalletFile (immutable after instantiation)
     */
    mutable CCriticalSection cs_wallet;
    const std::string strWalletFile;
    void LoadKeyPool(int nIndex, const CKeyPool &keypool)