O postfix é um substituto do sendmail que inclui seu próprio binário do sendmail (veja o rodapé deste post). Estou sinceramente surpreso em deixar você fazer isso, eu pensei que eles estavam em conflito de pacotes.
De qualquer forma, para corrigir:
sudo apt-get purge sendmail
sudo apt-get install --reinstall postfix
sudo /etc/init.d/postfix restart
A prova de que o sendmail no meu sistema é fornecido por postfix
:
$ dpkg -S 'which sendmail'
postfix: /usr/sbin/sendmail
Se você ainda está tendo problemas, veja como você pode descobrir qual programa (e qual pacote) está ocupando a porta 25:
$ sudo netstat -pel | grep smtp
tcp 0 0 *:smtp *:* LISTEN root 8487 2212/master
$ # Then we use the 2212 from that in the following to get the package:
$ dpkg -S "$(sudo ps ux | grep 2212 | awk '{print $NF}')"
postfix: /usr/lib/postfix/master
No meu caso, é o postfix. No seu caso, espero ver outra coisa. Nuke de órbita.