Cuenta los registros q da la consulta q estas haciendo .. y ahi le aplicas tu condicion .. Ejemplo:
Código:
$result=mysql_query("select * from gente WHERE sexo='$sexo' AND ciudad='$provincia'",$link);
$total_consulta_registros=mysql_num_rows($result);
if ($total_consulta_registros==0){
echo "no se encontraron coincidencias .. bal bla";
} else {
//resto de codigo con el while etc
}
Un saludo,