Bien el problema reside en el formato de la fecha.
Yo estoy usando un formato dd/mm/aa para crear las fechas, la base de datos en access tiene la fecha tambien en formato dd/mm/aa pero la consulta debo hacerla con formato mm/dd/aa

.
Así que antés de hacer la consulta sql hago lo siguiente:
Código PHP:
entrada= Month(entrada) & "/" & Day(entrada) & "/" & Year(entrada)
salida= Month(salida) & "/" & Day(salida) & "/" & Year(salida)
SQL="Select * from reservas where ((fecha_salida > #"& entrada &"# and fecha_entrada < #"& salida &"#))"
rs.open sql,objConn
Supongo que la explicación pueda estar en el motor Jet Database

, pero seguro que alguno de ustedes tiene una respuesta más precisa.
Un saludo
Kaki