This might be common knowledge already, but I've been able to get sendmail working on two different machines by following the instructions in /etc/mail/README. The catch is getting sendmail to start when starting the machine up. I just changed "MAILSERVER=-NO-" to "MAILSERVER=-YES-" in /etc/hostconfig, and now sendmail works again.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20020830054219202