On the machine that is running sendmail, you have to have a number of configuration files right of "there will be dragons."

First, I would insure that the forward and reverse DNS exists in both the /etc/hosts file and the DNS. Sendmail likes DNS, especially itself, to be configured correctly.

Sendmail normally tries to resolve its own hostname, but you can also enter it directly in the .cf file.

There is also a file, often located in /etc/mail/local-host-names which needs to have, of course, the local host names.

You can always post your files and we can have a look!

Neo