Idea...
Código PHP:
<?
$encontrado = false;
do
{
//armas nueva palabra
....$nombre = .....
//consultas por palabra
$sql = "SELECT nombre from publeje where nombre ='$nombre'";
$rs = mysql_query($sql);
if(mysql_num_rows($rs)!=0){
$encontrado = true;
}
}
while($encontrado == false);
echo 'Se ha encontrado el nombre: '.$nombre;
?>
Espero te sirva.
Saludos!