Reply кнопки имитируют отправку сообщения. Т.е. если вы нажмете на такую кнопку - это будет равносильно отправке текста вручную.
Поэтому если у вас есть какое-то количество кнопок, которые отвечают за какие-то определенные фразы, то просто в самом начале функции process_city_step проверяйте message.text на совпадение с нужными значениями. Если не совпадает ни с одним - удаляйте сообщение, либо сообщите пользователю об ошибке и еще раз вызывайте bot.register_next_step_handler(msg, process_fullname_step) , чтобы дать пользователю вторую попытку нажать на нужную кнопку, либо ввести нужное сообщение.
Но я бы на вашем месте рассмотрел вариант с Inline клавиатурой. Гораздо больше возможностей и не загромождает интерфейс. Да и проблемы с проверкой на доступные значения уже не будет.