Sadons

Лагать не будет. Мне кажется даже с обходом 1000 кнопок вы не увидете задержек.
Проблема в самом подходе.
Первое - вытаскивать все имена из БД чтобы потом посчитать сколько их было - ну такое себе. Гуглим SQL COUNT
Второе - если из строки task.8 нужно вытащить 8, то это проще сделать через split
call.data.split('.')[1]
И никакие циклы там не нужны (в данном случае и запрос в БД тоже не нужен).

Подучите больше основ чтобы не выполнять лишних действий.

select exists(select 1 FROM users WHERE id = <some_id>)

Это вернет true/false.

Потому что ты в обоих случаях прописываешь callback handler, обрабатывающий ВСЕ кнопки (так как в качестве func ты передаёшь предикат, всегда возвращающий истину, т.е. "я готов это обработать").
Далее, что значит "не помогло"?

@bot.callback_query_handler(func=lambda call: call.data.startswith('text'))

Вот прямо так и писал? или всё-таки заменял 'text' на что-то своё?
Потому что если так и писал, то ты тем самым сказал "вызывай этот обработчик для тех случаев, когда call.data начинается со слова text". У тебя ни в одном случае call.data не начинается с text.

Тут идея проста как два пальца: сделай иерархию в тексте call.data.
Например, в первом случае

item_yes = types.InlineKeyboardButton(text='Принять', callback_data='order_approve.yes')
item_no = types.InlineKeyboardButton(text='Отказаться', callback_data='order_approve.no')

Тут order_approve - что-то типа пространства имён, чтобы можно было отличать значения, приходящие по разным поводам (т.е. кнопки, обрабатываемые в рамках разных диалогов).
И тогда прописать обработчик можно будет так

@bot.callback_query_handler(func=lambda call: call.data.startswith('order_approve.'))

Во втором случае сделай по аналогии.

Error binding parameter 0 - probably unsupported type