Опитвам се да намеря превозни средства, които са свободни между 2 променливи дати

Използвате И, което означава, че и двете условия трябва да са верни. Вместо това трябва да използвате ИЛИ:

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

От друга страна, както е посочено от осветяването на синтаксиса, return е лошо име от име на колона. Това е запазена дума в Oracle и трябва да я избягвате, ако можете.