Próbuję znaleźć pojazdy, które są wolne między 2 różnymi datami

Używasz AND, co oznacza, że ​​oba warunki muszą być spełnione. Musisz zamiast tego użyć OR:

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

Z drugiej strony nie, jak wskazuje podświetlanie składni, return jest zły nazwa z nazwy kolumny. To zastrzeżone słowo w Oracle i powinieneś go unikać, jeśli możesz.