Descubra o arquivo que está sendo executado:
pgrep nginx | xargs -I{} readlink -f /proc/{}/exe
Então você pode expandir isso para descobrir a qual pacote esse arquivo (ou arquivos) pertence:
dpkg -S $(pgrep nginx | xargs -I{} readlink -f /proc/{}/exe | uniq)
No meu caso, isso destaca o pacote nginx-full
, mas pode ser que você encontre uma versão do Nginx que você instalou manualmente (não dos pacotes) e que agora você precisa remover manualmente.