Sobre validar ou não no cliente,
Você deve verificar se é um CPF válido no cliente para não onerar o backend, mas isso não quer dizer que você não deva fazer o mesmo no backend. Duplicidade de código sim, aumentar o nível de segurança e consistência do software, também. Saber se o CPF já está cadastrado, só no backend.
Agora, sobre como voltar mensagens para o cliente, como o exemplo que você deu, que o CPF já está cadastrado, depende do que você esta usando, mas de maneira geral deve ser no response HTTP ou socket. Pensando em segurança novamente, cuidado, pois ao expor que o CPF já está cadastrado, você pode estar dando essa informação para alguém mal intensionado e que talvez possa se aproveitar disso, inclusive fora do software.