Стоит использовать что-то в роде Memcached/Redis?
Мне в голову приходит только "из пушки по воробьям". Разве что, как сказал
zxscv , Memcached/Redis уже где-то используется, например для разделения сессий между инстансами бота.
где стоит хранить последнее выбранное меню/действие?
На какой срок нужно хранить это поле? Сколько инстансов бота должно иметь доступ к этому полю в 1 и тот же момент времени?
пользователь может закончить переписку в любой момент, а данные-то по-прежнему останутся в оперативной памяти
Почему бы не хранить состояние в текущем процессе бота (у Вас же есть сущность "сессия"?), а по тайм-ауту не скидывать его, скажем в обычный мускуль?