Devi eseguire una query del tipo (per la data in questione):

codice:
SELECT * FROM agenda WHERE NOT (OraInizio >= '$inizio' OR OraFine <= '$fine')
Dove $inizio e $fine sono gli orari di inizio e fine in formato HH:mm:ss.
Se la query NON restituisce risultati allora l'intervallo orario è libero e puoi effettuare la insert.