Hey Dan,
It looks like you’ve got everybody stumped. Not a whole lot of sendmail users around. 
Some things that I know:
saslauthd needs to be running
smtpd.conf (which could be anywhere and named something else, depending on the OS and version) probably needs to know about the relevant settings for authentication–specifically it’ll contain:
pwcheck_method: saslauthd
mech_list: PLAIN LOGIN
Note I say probably here, as it looks like Sendmail also includes these details in the configuration. So this file might just be for Postfix.
If you’re using user@domain.tld usernames, you’ll also need to add the -r to the FLAGS or OPTIONS field in /etc/sysconfig/saslauthd (Red Hat based systems) or /etc/defaults/saslauthd (Debian/Ubuntu).
So, that probably covers the saslauthd side. As for the Sendmail side…I’m not sure. The last time I used sendmail was before SMTP authentication existed, and we used POP-before-SMTP (which has always been a nasty hack).
Looks like the sendmail configuration looks something like this:
define(confAUTH_OPTIONS',
A p y’)dnl
TRUST_AUTH_MECH(LOGIN PLAIN')dnl define(
confAUTH_MECHANISMS’, `LOGIN PLAIN’)dnl
From there, we’ll want to get more detail from the logs. Maybe crank up debugging in Sendmail with:
define(confLOG_LEVEL',
14’)dnl
You can also get some very useful information by connecting with telnet, like this:
telnet localhost 25
Trying 127.0.0.1…
Connected to localhost.localdomain (127.0.0.1).
Escape character is ‘^]’.
220 virtualmin.com ESMTP Postfix
EHLO localhost
250-virtualmin.com
250-PIPELINING
250-SIZE 10240000
250-VRFY
250-ETRN
250-STARTTLS
250-AUTH PLAIN LOGIN
250-AUTH=PLAIN LOGIN
250 8BITMIME
Where the bold bits are the ones I typed. Everything else is from the server. We’re looking for the AUTH PLAIN LOGIN entry to let us know that at least the mail server is saying that it will allow SMTP auth.