"Domain ofe sender address root@linux.mydomain.com does not exit or resolve"
You are correct, your ISP's MTA (smart host) is testing the sender address sent by your MTA (probably the envelope sender) and it cannot resolve this to a name or IP.
The way I see it, you have a couple of choices:
1) Configure your MUA to set the proper sender address address. Possibly by setting the reply-to
2) Configure sendmail to masquerade as a valid domain name that can be looked up by your ISP's MTA.
If your using Redhat, see /etc/mail/sendmail.mc and look for the section regarding...
Code:
dnl # The following example makes mail from this host and any additional
dnl # specified domains appear to be sent from mydomain.com
dnl #
dnl MASQUERADE_AS(`mydomain.com')dnl
dnl #
dnl # masquerade not just the headers, but the envelope as well
dnl #
dnl FEATURE(masquerade_envelope)dnl
If you're not using Redhat, then you can add the MASQUERADE_AS and FEATURE statments above to your sendmail.mc file and change to meet the requirements of your ISP's MTA.