Делаем обычную сортировку по SORT, а дальше:
1 в шаблоне выводим только элементы с сортировкой меньше 23, остальные вываливаем в виде данных и рендерим на на странице js'ом (тупой вариант: выводить в тег script с невыполняемым type, и оттуда добавлять js'ом в страницу), страницы по набору элементов будут одинаковые, но порядок каждый раз будет разным. Кэш работает.
2 Добавляем 2-4 дополнительных свойства скажем SORT1, SORT2 и т.д. зафигачиваем эти свойства случайными числами и делаем вторую сортировку по одному из них. При этом выбираем по какому именно рандомно. Получаем 4 кэша с разными страницами по составу.
3 Раз в сутки ночью, агентом переписываем эти допсвойства на другие случайные значения.
Итого: кэш работает, видимость случайности есть, причем она при каждом обновлении разная и даже хрен поймешь что страницы часто одинаковы по составу. Объем кэша каталог вырастит - ну у всего есть цена.
UPD:
Про решение с двумя компонентами - да просто во втором компоненте на первой странице скройте 22 элемента первые и все. Естественно страница должна быть больше 22 элементов.
Возможно вы сразу возразите, что тогда посетитель в постраничной выборке не увидит эти 22 элемента, поэтому сразу отвечу - вас это вообще не должно волновать, так как у вас посетитель вообще не увидит почти половину каталога (так на вскидку 40-45%) при случайной выборке + пагинации. Вообще пагинация при настоящей случайной выборке полностью лишена смысла.
Рабочее решение близкое к вашим требованиям я выше привел.
Если хотите избавится в нем от того что часть элементов каталога будет невидна при пагинации - передавайте в свойствах пагинации еще и свойство сортировки случайно выставленное на первой стартовой странице.
