Осталось понять, почему MEMORY-таблица сессий упорно отказывается использовать индексы для выборки и сортировок. Там правда 1500 записей всего, из которых регулярно выбирается 500-700. Возможно, оптимизатор mysql забивает на индексы, потому что без них быстрее получается.
В таких таблицах по умолчанию используется другой тип индекса - HASH. Который умеет только искать конкретное значение, но зато очень-очень быстро.
По идее можно сделать и BTREE индекс, но для такого кол-ва записей это особого смысла не имеет.