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.

{
    bitdb.Flush(shutdown);
}
bool CWallet::Verify()
{
    if (GetBoolArg("-disablewallet", DEFAULT_DISABLE_WALLET))
        return true;
    LogPrintf("Using BerkeleyDB version %s\n", DbEnv::version(0, 0, 0));
    std::string walletFile = GetArg("-wallet", DEFAULT_WALLET_DAT);
    LogPrintf("Using wallet %s\n", walletFile);
    uiInterface.InitMessage(_("Verifying wallet..."));
    
    if (walletFile != boost::filesystem::basename(walletFile) + boost::filesystem::extension(walletFile))
        return InitError(strprintf(_("Wallet %s resides outside data directory %s"), walletFile, GetDataDir().string()));
    if (!bitdb.Open(GetDataDir()))
    {
        
        boost::filesystem::path pathDatabase = GetDataDir() / "database";
        boost::filesystem::path pathDatabaseBak = GetDataDir() / strprintf("database.%d.bak", GetTime());
        try {
            boost::filesystem::rename(pathDatabase, pathDatabaseBak);
            LogPrintf("Moved old %s to %s. Retrying.\n", pathDatabase.string(), pathDatabaseBak.string());
        } catch (const boost::filesystem::filesystem_error&) {
            
        }
        
        
        if (!bitdb.Open(GetDataDir())) {