Depende. E você não precisa abrir mão de uma coisa para ter outra.
Por exemplo, numa API usada por terceiros, você certamente vai querer os possíveis cenários excepcionais bem definidos e documentados, desta forma quem for usá-la pode realizar os tratamentos como melhor convier.
Entretanto, num sistema comum, remover algo que já foi removido pode ser algo simplesmente a ser ignorado. Por exemplo, um usuário, utilizando uma tela de cadastro num sistema web, clica várias vezes no botão "Excluir" porque a internet está lenta. Como resultado várias requisições chegam excluindo o mesmo objeto. A primeira vai surtir efeito e as demais mostram o erro de que o objeto não foi encontrado. Como o usuário vê apenas o resultado da última requisição, ele pode chegar à conclusão de que tem algum problema com os sistema.
Além disso, se você achar adequado, pode ter uma exceção genérica como ErroCadastroException
que é lançada sempre que uma operação não permitida for executada, tal como adicionar um registro duplicado ou alterar algo que não existe.
Porém, suponha que você depois vê a necessidade de incluir uma validação específica para verificar se o valor de um campo é duplicado, de forma a mostrar para o usuário exatamente qual é o problema. Neste caso, poderia criar especificamente uma exceção que estenda a outra e contenha o erro em específico. Por exemplo:
public class CpfJaExisteException extends ErroCadastroException {
...
}
Desta forma, você pode mostrar uma mensagem amigável para o usuário, por exemplo informando que aquela pessoa já possui cadastro ou mesmo redirecionando para o cadastro dela.
Um ponto importante aqui é que provavelmente você pode usar tal exceção nas rotinas internas do sistema, mas irá tratá-la em algum momento para tomar a ação necessária.
Em resumo, você deve criar as exceções somente se pretende tratá-las especificamente em algum ponto, caso contrário use uma exceção genérica.
Note também que há alternativas para exceções. Por exemplo, se não houver dados numa tabela, retorne uma lista vazia. Na tela, você pode verificar se existem ou não registros retornados e exibir alguma mensagem dizendo que não há registros retornados.