How are the partitions defined? I'm thinking that is must be range based, and that the predicate departure_date>to_date('31-DEC-2004','DD-MON-YYYY') would actually be better as departure_date>=TO_DATE('01-JAN-2005','DD-MON-YYYY')

This would be because your current predicate is not fully eliminating the possibility of there being some results required from the 2004 partition. How does that sound?