El optimizador no debería elegir usar el índice en EMP.DEPT_ID en la segunda consulta, ya que puede tener valores NULL. Esto es lo que hace que se excluya una fila de los resultados.
La única explicación que no es un error que puedo pensar en este momento es que de alguna manera ha creado restricciones en el modo DISABLE RELY para que el optimizador piense que el campo no puede contener valores NULL. En este caso, sería correcto usar el índice dada la información incorrecta en las restricciones. Sin embargo, parece que la opción RELY no está disponible para las restricciones NOT NULL, por lo que no veo cómo podría ser este el problema. No obstante, observe detenidamente todas las restricciones de las tablas.
Aparte de eso, hay una cantidad sorprendente de errores en el sitio de Oracle con respecto a los resultados incorrectos de las uniones externas completas. Podrías estar golpeando a uno de ellos. En bastantes de estos casos, la solución es deshabilitar las uniones externas completas "nativas", lo que puede hacer para su sesión actual con esta declaración:
alter session set "_optimizer_native_full_outer_join"=off;
