Итак, отчет по моей эпопее)
Посоветовались с Монсом (грац), сделали первичный ключ вида {timestamp}{random string} - 162343243abcdef
Файбер очистки идет периодически и автоматом получает самые старые сесии в порядке возрастания. Как только находим сессию, где timestamp == now, прерываемся. (ну или прервемся, если достигли лимита на один проход, я его поставил 1млн)
Таким образом мы не сидим очень долго в итераторе и он не подвисает (тут я думаю, все же особенности архитектуры или баг - что итератор в итоге тупит)