Snažíme se najít vozidla, která jsou volná mezi 2 proměnnými daty

Používáte AND, což znamená, že obě podmínky musí být pravdivé. Místo toho musíte použít OR:

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

Na straně ne, jak naznačuje zvýraznění syntaxe, return je špatné název z názvu sloupce. Je to vyhrazené slovo v Oracle a měli byste se mu vyhnout, pokud můžete.