Muito provável /usr/bin/pdflatex é um link simbólico para o pacote que você acabou de remover, que, por sua vez, não existe . Tente ls -l /usr/bin/pdflatex para ver se aponta para outro arquivo. Se é um link simbólico quebrado (o alvo não existe) você pode simplesmente removê-lo e o próximo pdflatex no PATH deve ser executado.
which realmente procura o primeiro executável no PATH , que existe . Em outras palavras, se você ln -s /non-existing/path /usr/local/sbin/pdflatex será ignorado por which , mesmo que /usr/local/sbin seja o primeiro em PATH .