Você terá que encontrar manualmente os arquivos, o que provavelmente seria o que o deluser faria.
Por favor, note que --remove-all-files não é igual a rm -r /home/user . O último apenas remove o homedir (que pode incluir arquivos não pertencentes a esse usuário, embora não sejam usuais), o primeiro remove todos os arquivos de propriedade daquele usuário do sistema. Pelo menos se a página do manual for confiável .
O GNU find tem um teste -user , portanto, você pode fazer find / -user xxx para localizar todos os arquivos de propriedade do usuário xxx . xxx seria o nome do usuário e pode (e, nesse caso, terá que ter que, como o usuário não existe mais) ser o ID numérico do usuário. find também tem uma opção -delete , então
find / -user xxx -delete
Deve fazê-lo, embora eu não tenha testado o comando com todas as opções ao mesmo tempo.
EDIT: ID numérica: A razão pela qual eu disse que você tem que usar um ID numérico é porque, como você já deletou o usuário, a entrada dele em /etc/passwd foi deletada (tinha, ao longo com outras coisas, o ID do usuário, juntamente com seu nome de usuário).
Então, se você não removeu o seu homedir, uma das maneiras mais fáceis é apenas consultar o ID do proprietário do homedir:
stat -c %u /home/user/
( stat é uma ferramenta para ler dados do sistema de arquivos. -c %u informa stat como escrever sua saída, aqui estou pedindo para simplesmente gerar o ID do usuário)
Se você gosta de one-liners, você pode até encadear os dois comandos:
find / -user $(stat -c %u /home/user/) -delete
(Claro que você pode preferir executá-lo primeiro sem -delete para ter certeza de que não há nada que você queira manter, e para pegar qualquer erro que tenha cometido ao escrever o resto do comando. Erros ao fazer operações de exclusão recursivas em / não são para cardíacos.)