Проблема была в библиотеке, которую я использовал
https://github.com/php-telegram-bot/core
Если получать апдейты из телеграма при помощи метода этой библиоткеи handleGetUpdates(), то библиотека сама отправляет пустые ответы на CallbackQuery.
Получается, что я пытался ответить на тот же CallbackQuery еще раз, ответ от Телеграма приходит - ОК, а реально Телеграм обрабатывал только первый ответ, который автоматически слала библиотека.
