Você deve ter usado o instalador .msi. Ele registra automaticamente um serviço do Windows que inicia instantaneamente após a instalação (pelo menos na minha máquina win 10).

Este serviço usa a configuração padrão e se vincula à porta 6379. Quando você inicia o redis-server a partir da linha de comando, se você não especificou uma porta diferente por meio de um arquivo de configuração, ele pega a configuração padrão novamente e tenta se vincular à porta 6379 que falha.

Seu cli funciona porque ele se conecta ao serviço redis que já está escutando em 6379. Seu comando de desligamento interrompe o serviço e, a partir daí, as coisas funcionam conforme o esperado. Mistério resolvido. Caso encerrado.