AOLServer sends out odd-looking HELO statements to SMTP servers (e.g., "AOLServer?domain.com"), which might be causing problems. I use qmail and haven't seen trouble with this, but I imagine that Sendmail might choke on it.
I also seem to recall seeing odd "From" addresses in the SMTP envelope from ns_sendmail. I hope that I'm wrong, but it could be that Sendmail doesn't like something there.
