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.

void KeepKey(int64_t nIndex);
    void ReturnKey(int64_t nIndex);
    bool GetKeyFromPool(CPubKey &key);
    int64_t GetOldestKeyPoolTime();
    void GetAllReserveKeys(std::set<CKeyID>& setAddress) const;
    std::set< std::set<CTxDestination> > GetAddressGroupings();
    std::map<CTxDestination, CAmount> GetAddressBalances();
    CAmount GetAccountBalance(const std::string& strAccount, int nMinDepth, const isminefilter& filter);
    CAmount GetAccountBalance(CWalletDB& walletdb, const std::string& strAccount, int nMinDepth, const isminefilter& filter);
    std::set<CTxDestination> GetAccountAddresses(const std::string& strAccount) const;
    isminetype IsMine(const CTxIn& txin) const;
    CAmount GetDebit(const CTxIn& txin, const isminefilter& filter) const;
    isminetype IsMine(const CTxOut& txout) const;
    CAmount GetCredit(const CTxOut& txout, const isminefilter& filter) const;
    bool IsChange(const CTxOut& txout) const;
    CAmount GetChange(const CTxOut& txout) const;
    bool IsMine(const CTransaction& tx) const;
    
    bool IsFromMe(const CTransaction& tx) const;
    CAmount GetDebit(const CTransaction& tx, const isminefilter& filter) const;
    CAmount GetCredit(const CTransaction& tx, const isminefilter& filter) const;
    CAmount GetChange(const CTransaction& tx) const;
    void SetBestChain(const CBlockLocator& loc);
    DBErrors LoadWallet(bool& fFirstRunRet);
    DBErrors ZapWalletTx(std::vector<CWalletTx>& vWtx);
    DBErrors ZapSelectTx(std::vector<uint256>& vHashIn, std::vector<uint256>& vHashOut);
    bool SetAddressBook(const CTxDestination& address, const std::string& strName, const std::string& purpose);
    bool DelAddressBook(const CTxDestination& address);
    void UpdatedTransaction(const uint256 &hashTx);
    void Inventory(const uint256 &hash)