mmm... podrias llenar un array con todos los id que tengas seleccionandolos de una consulta y luego generar un numero aleatorio y utilizar ese aleatorio como la clave del array para obtener en id de esa posicion algo asi
Código PHP:
$ID_vector; //suponiendo que contiene los todo los id (1=>1,2=>2,3=>5,4=>6...etc...);
$num_ids=count($ID_vector);//numero de id's
$aleatorio=rand(0,num_ids-1);//obtenemos un aleatorio
$id_aleatorio=$ID_vector[$aleatorio]; //utilizamos ese num aleatorio para obtener el id de esa posicion