select surname,firstname into x_surname,x_firstname from departure_all
where ((fullname like v_1) or
(fullname like v_2))
and trunc(departure_date+0) >'31-DEC-04' and rownum<2

Flush your shared pool before this. I know this column is not having index. But just a try.