In the true sprit of UNIX and expecially BSD (which is known for greater than 365 days of uptime) rebooting the entire box just to start sendmail is not necessary. Since the only thing the /System/Library/StartupItems/Sendmail/Sendmail script does is start sendmail, we can execute it manually from the command line with:
sudo ./System/Library/StartupItems/Sendmail/Sendmail start
the ./ preceding the full path is necessary. This is the way to tell the shell to execute the script since it is not a proper binary-executable file.
Rebooting is for OS 9 boxes and Windows, c'mon.