This happened to me when I switched our domain from "linux.usu.edu" to "fslc.usu.edu" (still have linux.usu.edu as alias). The thing is that when the computer services folks here at USU changed the DNS entries, they did not add "linux.usu.edu" as alias as I had requested.
All my AOLserver files had linux.usu.edu back then and I started getting these errors. I edited the AOLserver files to reflect fslc.usu.edu and it disappeared. Later the DNS entries for "linux.usu.edu" were added as well.
Do you have the "MailHost=" param right in your config file ? I am not 100% sure how ns_sendmail works. Doesn't it call your MTA ? If so, check if your MTA is well.
Hope this helps.
