Observando /etc/passwd nos backups feitos de seu sistema a partir do dia / semana / período antes da exclusão do usuário.
Se userdel foi usado com -r, o diretório inicial e o spool de correio do usuário desapareceram. Se não foi usado com -r, verifique o spool de correio do usuário ou talvez um crontab se tiver muita sorte.
Se não houver backups e nenhum arquivo óbvio pertencente a esse usuário puder ser verificado, será necessário procurar locais como /tmp e procurar arquivos com UIDs como proprietários e tentar resolvê-los. na verdade, seu backup é sua melhor aposta.
Edit: como jw013 indica, você também pode usar find / -nouser para encontrar arquivos que não tenham nenhum usuário correspondente para o UID do arquivo.