la data in mysql viene memorizzata in effetti in formato americano, cioè come hai detto tu anno-mese-anno. Ma con in mezzo il trattino, non il / ricordalo..
Se quindi chiedi una data in formato giorno-mese-anno puoi fare come hai fatto tu con explode o ancora meglio con la funzione date (http://it2.php.net/manual/en/function.date.php) :

Codice PHP:
$INIdata = explode("/",$_POST['data_inizio']);//data presa dal form inviato 
$INIgiorno = int($INIdata[0]);//questo dovrebbe essere il giorno (1); 
$INImese = int($INIdata[1]);//questo il mese (12); 
$INIanno = int($INIdata[2]);//questo l'anno (2008); 
$MYSQLdata = date("Y-m-d", mktime(0, 0, 0, $INImese, $INIgiorno, $INIanno));// scriverà 2008-12-01 
la funzione MKTIME (http://it2.php.net/manual/en/function.mktime.php) rappresenta una dtaa in formato unix e unita a DATE puoi formattarla come meglio ti pare. Anzi, le due funzioni insieme ti permettono di fare calcoli su date, ad esempio

Codice PHP:
<?php
echo mktime(0, 0, 0, date("m")  , date("d")+1, date("Y"));// visualizza il giorno domani
echo mktime(0, 0, 0, date("m")-1, date("d"),   date("Y"));// visualizza la data di un mese fa
echo mktime(0, 0, 0, date("m"),   date("d"),   date("Y")+1);// visualizza la data fra un anno
?>

IL metodo che scrivi per ottenere le disponibilitàò un buon mezzo ma forse è meglio confrontare due date. Avendo a disposizione $INIdata e $FINdata puoi scrivere

Codice PHP:
$query="SELECT date FROM prenotazioni WHERE date>='$INIdata' AND date <='$FINdata'"; 
come risultato avrai un array con tutte le date comrpese fra quelle due.