Lo que puedes hacer es la consulta por ese "ramdom" que generas .. y comprobar q arroja la consulta 1 registro .. si no arroja al menos un registro .. repites la consulta:
Código PHP:
While ($total<=1){
$sql="SELECT * FROM tabla WHERE id=rand()";
$consulta=mysql_query($sql);
$total=mysql_num_rows($consulta);
}
// en este punto ya tiene q haberte devuelto un registro aleatorio q exista ..
// Ya puede hacer tu mysql_result() o si te gusta tu $row=mysql_fetch_xxx
// para obtener tus campos de tu registro.
Un saludo,
pd: jeje si va avisa ..q lo hice al vuelo xD