Buenas tardes moscrates, me imagino que con PHP generas un ID aleatorio y después haces un select con ese ID:
Pero como bien dices, aquí el problema es que PHP no tiene control sobre qué valores aparecen en la tabla.
Lo que se me ocurra es que le dejes la parte de la generación de aleatorios también a MySQL, es decir, puedes hacer algo como esto
Select * from TuTabla Order by RAND() Limit 1
Esto te regresará un registro de tu tabla al azar, haz la prueba a ver si es lo que necesitas. Lo otro que se me ocurre es que pongas un ciclo donde generas tu aleatorio con PHP hasta que la consulta te regrese algún registro, pero esto me parece muy óptimo.
Saludos
Leo.