Что-то я не очень понимаю, что значит "вывод из базы инфы в случайном порядке и с постраничным выводом"??
Если ты хочешь на каждой странице делать запрос, то никак. Точней надо как-то исключать возможность выбора того что уже было выбрано на предидущей странице. И переход по страницам будет строгий. с превой тока на вторую.
Либо делай выборку с ORDER BY RAND() суй массив выборки в сессию например, и пагинатором выбирай соответствующие ячейки массива
Или доставай просто SELECT * FROM `Table` LIMIT 1,20
Далее набираешь выорку в массив и делаешь shuffle()
Вот что сразу в голову приходит
=========================================
$sql = mysql_query ("SELECT * FROM table WHERE id='444' order by rand() LIMIT 1, 20");
Что то я не пойму??? Ты достаешь из таблицы table запись с id=444 и хочешь чтоб их там много было?? Или как? Тут ни ORDER ни LIMIT не нужен. Если у тя конечно уникальные id