Beh intanto la query dovresti farla con un order by che già predisponga i villaggi per regione
codice:
SELECT .... FROM Village WHERE ....ORDER BY idRegione, nome
Dopodichè nel ciclo fai un controllo sul valore di idRegione del record corrente:
se è diverso da quello del record precedente stampi un <optgroup>, altrimenti non lo stampi.
Codice PHP:
$previous_region = -1;
while($dati=mysql_fetch_array($r)){
if($previous_region != $dati['idregione']) //Ovviamente metti il nome giusto al posto di 'idRegione'
print "<optgroup>" . $dati['nomeRegione'] . "</optgroup>\n";
$previous_region = $dati['idregione'];
$idr[id_village]=$dati[id];
$idr[bloccato]="no";
$rt=trova($idr,'outlet_temp');
if (mysql_num_rows($rt)>0) print "<option value=\"$dati[id]\">$dati[nome]</option>\n";
}
Come commentato, devi ovviamente sostituire 'idRegione' con il nome dell'attributo dell'id che indica la regione.
Inoltre se vuoi stampare il nome della regione dovrai ovviamente fare una JOIN tra la SELECT dei villaggi, insieme alla tabella delle regioni, in modo da ottenere il nome delle stesse.
Ciao 
PS - Ah comunque cerca di formulare meglio le domande e di includere il codice che riporti in un blocco delimitato dai tag giusti: [ php] e [/ php] (che io scrivo con gli spazi, altrimenti non te li stampa... guarda nella toolbar dell'editor di testo comunque...).