This one had me scratching my head for a little while so is worthy of a note here.
SunOS 5.9 running sendmail was already relaying email to example.domain.com, but a request was received to change this to newmail.domain.com (domain names changed here).
Naturally, I amended the DS entry in /etc/mail/sendmail.cf and restarted sendmail with /etc/rc2.d/S88sendmail stop then /etc/rc2.d/S88sendmail start. However, /var/log/syslog was telling that sendmail was still routing to example.domain.com. Grrr.
To fix this I also changed the DS entry in /etc/mail/submit.cf and that did the trick. 🙂