Стандартно в битриксе пагинация построена через get параметр PAGEN_1=2, где 1 это номер пагинации, а 2 это номер страницы.

Для чего нужен номер пагинации? Если на странице есть несколько компонентов с пагинацией у первого компонента параметр будет равен PAGEN_1, у второго PAGEN_2 и т.д. что бы при переключении страницы у одного компонента, другие отображали прежний результат.

Заметили проблему: на странице каталога выбираем номер страницы, все отрабатывает корректно, выбираем другой номер и пагинация перестает работать. И так далее - то работает, то не работает, нет никакой закономерности.

Шаблон и сам компонент system.pagenavigation стандартный.
Смотрим массив $arResult, NavNum (номер пагинации) = 4, обновляем страницу NavNum все так же 4, еще раз обновляем и тут NavNum становится 2.

Пересмотрели все компоненты выше каталога, ни один из них не использует пагинацию.
Лезем в ядро и смотрим где и как определяется этот NavNum. Выяснилось, что при каждом вызове метода InitNavStartVars() параметр NavNum просто инкрементируется. Ну ладно инкрементируется и инкрементируется, но у нас же на странице только один компонент использует пагинацию, откуда же берется номер 4?
Вставляем в функцию debug_backtrace() и смотрим откуда идут вызовы.

Оказалось на сайте есть агенты которые использует CIBlockElement::GetList() и если передать параметр nPageSize, то происходит вызов InitNavStartVars() и растет инкремент у NavNum.
А так как агент отрабатывает не на каждом хите, то NavNum меняется периодически и пагинация не срабатывает.

Так что, при появлении подобной проблемы в первую очередь обратите внимания на места в коде использующие CIBlockElement::GetList() с параметром nPageSize