O otimizador não deve optar por usar o índice em EMP.DEPT_ID na segunda consulta, pois pode ter valores NULL. Isso é o que está causando a exclusão de uma linha dos resultados.
A única explicação não-bug que posso pensar no momento é que você de alguma forma criou restrições no modo DISABLE RELY para que o otimizador pense que o campo não pode conter NULLs. Neste caso seria correto usar o índice dado a informação incorreta nas restrições. No entanto, parece que a opção RELY não está disponível para restrições NOT NULL, então não vejo como isso pode ser o problema. No entanto, dê uma olhada cuidadosa em todas as restrições nas tabelas.
Além disso, há um número surpreendente de bugs no site da Oracle relacionados a resultados errados de junções externas completas. Você pode estar acertando um deles. Em alguns desses casos, a solução alternativa é desabilitar as junções externas completas "nativas", o que você pode fazer para sua sessão atual com esta instrução:
alter session set "_optimizer_native_full_outer_join"=off;
