This should help you completely uninstall Sendmail and all that comes with it.
First, stop the service (assuming it's running).
sudo /etc/init.d/sendmail stop
Uninstall sendmail and sendmail-bin
sudo apt-get remove sendmail sendmail-bin
After running that, the output said procmail was installed with Sendmail and can be uninstalled. So, I ran this command to remove procmail.
sudo apt-get remove procmail
After removing procmail, the output said sendmail-base m4 sendmail-cf and libdb4.8 were installed with procmail and can be uninstalled. So, I ran this command to remove them.
sudo apt-get remove sendmail-base m4 sendmail-cf libdb4.8
Even after all that, we still have some files on our server we didn't want. So we have to perform a purge.
sudo apt-get purge sendmail sendmail-bin
Finally, a reboot is required.
sudo reboot
After the reboot, your box should be completely rid of sendmail.