Intentando encontrar vehículos que estén libres entre 2 fechas variables

Está utilizando AND, lo que implica que ambas condiciones deben ser verdaderas. Debe usar O en su lugar:

select vehicle_registration
  from trips
 where departure not between :departure and :return
    or return not between :departure and :return

Por un lado no, como indica el resaltado de sintaxis, return es un malo nombre de un nombre de columna. Es una palabra reservada en Oracle y debe evitarla si puede.