Варианты ниже. Мне нравится 5й.
1. Можно все таки ввести неразрывный ключ, хранить его в отдельной таблице, пересчитывать его при каждом удалении/добавлении.
2. Сегментирование по датам, по месяцам - внутри каждого сегмента своя пагинация
3. Если не нужна возможность перехода на произвольную страницу - следующая страница это
... where id < $min_id limit 30
где min_id - минимальный id на текущей странице.
4. если число элементов на странице фиксировано - можно хранить справочную таблицу (номер страницы,стартовый id, конечный id) обновлять её при удалении/вставке/по крону
5. применить гибридный подход: я крайне сомневаюсь что бизнес требования подразумевает offset на 900000 строк. Соответствено первые n тысяч записей можно пролистывать через offset, а дальше - по датам например. Так работает livejournal.
