The problem with your code is that you don’t repeat the check to find an X file that doesn’t exist in the directory. Inside your function verifica() for example, you increment the variable x if the file already exists, but you do not call the function again.
To solve the problem you can create a repetition block or use recursion to repeat the check as many times as necessary. See below some examples:
Using recursiveness:
import os
def verifica(arquivo, x = 0):
    if os.path.exists(arquivo.format(x)):
        return verifica( arquivo, x + 1 )
    else:
        # Ao invés de retornar só o número, ele já retorna
        # o nome de arquivo formatado.
        return arquivo.format(x) 
enc = 'UTF-8'
# A função input já retorna por padrão uma string, então não é necessário
# converter o dado obtido para str().
decisao = input("Quer criar um novo usuario? ").lower()
# Verifica se a decisão começa com a letra "s".
if decisao.startswith('s'):
    nome_de_arquivo = verifica(r"C:\Users\danie\Desktop\saida\{}.txt")
    arquivo = open(nome_de_arquivo, 'w', encoding = enc)
    arquivo.write('Teste de texto')
    arquivo.close()
Using a repeating block:
# Como estamos utilizando um bloco de repetição, não é necessário criar a função verifica().
if decisao.startswith('s'):
    x = 0
    nome_de_arquivo = r"C:\Users\danie\Desktop\saida\{}.txt"
    while True:
        if os.path.exists(nome_de_arquivo.format(x)):
            x += 1
        else:
            break
    arquivo = open(nome_de_arquivo.format(x), 'w', encoding=enc)
    arquivo.write('Teste de texto')
    arquivo.close()
If you also want to limit the amount of X files in your directory, just replace the block while by a for..range(limite) thus:
if decisao.startswith('s'):
    limite = 1000  # Limite de 1000 arquivos
    nome_de_arquivo = r"C:\Users\danie\Desktop\saida\{}.txt"
    x_arquivo = None
    for x in range(limite)
        if not os.path.exists(nome_de_arquivo.format(x)):
            x_arquivo = x
    if x_arquivo:
        arquivo = open(nome_de_arquivo.format(x), 'w', encoding=enc)
        arquivo.write('Teste de texto')
        arquivo.close()
    else:
        print("ULTRAPASSOU O LIMITE!")