Тоже недавно столкнулся с этой проблемой и нашел для себя вполне приемлемый выход из этой ситуации с ограничением в 64 байта. Можно сделать md5() строки и сохранить в кеш. Redis(предпочтительно так как позволяет из коробки еще и задать срок жизни), файловый или еще какой - это уже не важно. Потом при нажатии на кнопку, берем из cb_data md5 и по нему берем значение. Может кому пригодится.
Вот буквально только что пришлось на скору руку фиксить бота, в котором не учел максимально допустимую длину cb_data.
p.s. Стоит наверное уточнить, что можно словить коллизию, но если у вас не бот на миллиарды запросов в день, то вас это не коснется:)
p.s.s. Вместо md5 можно получать более стойкий к коллизии хэш, например hexdec(hash('crc32', $str) . hash('crc32b', $str)) (php) или crc64
p.s.s.s. Если вероятность коллизий вас все же смущает тогда стоит сделать инкрементный уникальный ключ и по нему хранить callback_data.