Hola! 
 
Aplico logica de programador porque, al fin y al cabo, eso soy, jejeje. La consulta la entiendo perfectamente, te has explicado genial. 
Esta es la consulta que he genereado:  
 Código PHP:
    
$consulta="SELECT * FROM vehicles V 
INNER JOIN reserves R ON V.matricula = R.matricula 
WHERE 
  NOT ('".$dia_recollida_BBDD."' BETWEEN R.data_inici AND R.data_fi) 
  AND NOT ('".$dia_desti_BBDD."' BETWEEN R.data_inici AND R.data_fi) 
  AND V.disponibilitat = 1 
  AND V.oficina = '".$oficina_recollida."' 
  AND V.classe = '".$tipus_vehicle."'
  GROUP BY V.matricula  
  LIMIT $inicio, $registros"; 
    
  El problema que me surge ahora es que solo me salen los vehículos de la tabla "reservas" y lo que yo quiero es que me salgan los vehículos que están en la tabla "vehiculos" pero no tienen reserva para el periodo introducido por el usuario... 
Pues eso, voy a seguir investigando. Si se os ocurre algo estaré muy agradecido. 
Muchas gracias!