Zamiast pokazywać tylko losowy rekord, wybierz identyfikator rekordu i wykonaj przekierowanie do wersji, która pokazuje ten identyfikator.
$randomId = // whatever method you use to choose it
header( "Location: http://site.com/index.php?id=$randomId" );