I figured out how to solve this problem. I'm not entirely sure what caused it in the first place, but I did determine some differences between the server and the desktop and was able to use that to solve my problems.
First, on the server, sendmail had been changed to run only on run level 4 - while on the desktop it runs on 2, 3, 4 and 5.
I ran the following to reset sendmail to match the desktop.
sudo chkconfig --levels 235 sendmail on
After this, simply restarting the sendmail service made sendmail work.
sudo service sendmail restart