Here's one possible problem: There is a line in your sendmail.tcl with "Helo AOLserver [ns_info hostname]". You should change this to "Helo [ns_info hostname]". This is an AOLserver bug that has been reported but not yet fixed.
http://sourceforge.net/tracker/index.php?func=detail&aid=632265&group_id=3152&atid=103152
