Dopo che esegui la query (che se corretta e non trova niente va a buon fine) e prima del ciclo while, puoi controllare l'effettivo numero di records estratti con mysql_num_rows($result): se ti ritorna 0, vuol dire che la query è andata a buon fine ma non ha trovato alcun riscontro con i parametri di ricerca. In questo caso mandi il messaggio di avviso, altrimenti entri nel ciclo while e mostri i risultati