Edit following in /etc/mail/sendmail.cf and add the name of your outgoing/relaying mailhost. Ensure that the relay server is accepting your email first.
# "Smart" relay host (may be null) DS
e.g. if the outgoing relay is mailhost.xyzserver.com sendmail configuration should look like following.
# "Smart" relay host (may be null) DS mailhost.xyzserver.com
After that restart the sendmail.
/etc/init.d/sendmail stop /etc/init.d/sendmail start
