Você está usando AND, o que implica que ambas as condições devem ser verdadeiras. Você precisa usar OR em vez disso:
select vehicle_registration
from trips
where departure not between :departure and :return
or return not between :departure and :return
De um lado não, conforme indicado pelo realce de sintaxe,
return é um ruim nome de um nome de coluna. É uma palavra reservada no Oracle e você deve evitá-la se puder. 
