Parece que você tem um alias ou uma função de shell com esse nome; Acredito que os dois ignorariam seu $ PATH e ficariam escondidos de 'which'.
Para verificar um alias:
alias redis-cli
Para excluir um alias, se você encontrar um:
unalias redis-cli
Para verificar uma função:
declare -f redis-cli
Para excluir uma função, se você encontrar uma:
unset -f redis-cli
Se um deles for o problema, esses comandos só ajudarão até o final da sessão de terminal e você terá que executá-los novamente na próxima vez. Você vai querer verificar o seu .bashrc e .profile para ver se há algum comando falso que mencione o redis-cli. Se isso não funcionar, eles podem estar em algum lugar em / etc.
grep redis-cli /etc