Vale.
Y el problema que tienes, era el max_time_execution está a 30. Puedes cambiarlo únicamente para este script, poniendo al principio:
Código PHP:
ini_set("max_execution_time",0);
Así no se "detendrá" hasta que encuentre un hueco, por ejemplo.
Ahora, sigo pensando q lo más limpio es buscar primero si hay algun hueco disponible (si de 100 huecos, por ejemplo, hay 5 disponible.... q te salgan por random es complicado!).