I will not post the whole process of sendmail configuration here, just would like to pay attention to a small detail.
/etc/mail/local-host-names is a text file, that contains the list of domain names and it is taken by sendmail when checking outgoing mail. You should make sure you have this file in the following format:
# local-host-names sample file
# end of file
Please, note, that you should leave the comment on the last line as it is ignored by sendmail. Your local-host-names should have the last line either blank, either commented. Hope this saves someone some time, as this feature is not so well documented and you might have problems with the last domain in the list.