1)Make sure that the server has a Fully Qualified Domain Name (FQDN).
2)route ADD "network" MASK "subnet mask" "gateway ip"
3)make sure you have mailhost defined in your naming system (local files, NIS, NIS+, DNS, etc.).

Our change was to the sendmail.cf file as follows:

1. Peform the following on the subject systems.

# cd /etc/mail/cf/cf
# cp sendmail.mc `hostname`.mc
# cp submit.mc `hostname`.submit.mc

2. modify `hostname.mc as follows:

Change the current entry, listed below, to reflect the new entry listed
below:

Current entry:

define(`confFALLBACK_SMARTHOST', `mailhost$?m.$m$.')dnl

New entry:
define(`SMART_HOST', `mailhost$?m.$m$.')dnl

3. After the change:
# make `hostname`.cf `hostname`.submit.cf

4. Make a backup of the existing sendmail files in /etc/mail.
# cd /etc/mail
# cp sendmail.cf sendmail.cf~
# cp submit.cf submit.cf~

5. Copy the newly edited files.
# cd /etc/mail/cf/cf
# cp `hostname`.cf /etc/mail/sendmail.cf
# cp `hostname`.submit.cf /etc/mail/submit.cf

restart sendmail daemon/service