Since sendmail.cf has mailhost in it, it's looking for a server called mailhost OR a DNS cname for mailhost.
This is what you need to do:
If you want to fix it in the sendmail.cf file, change mailhost to be the name of the mail server (what ever that is). Post back what it had in there just to make sure it's what you are looking for -
If you want to fix it in DNS, then you have to do a couple of things:
Post back what is in sendmail.cf for mailhost (the whole line).
Set up a MX record and set up mailhost to an IP of a system.
To see this, do a nslookup
% nslookup
Default Server: which1.mycom.com
Address: 10.140.16.20
> set type=mx
> ibm.com
ibm.com preference = 0, mail exchanger = ns.watson.ibm.com
ibm.com nameserver = ns.watson.ibm.com
ibm.com nameserver = ns.austin.ibm.com
ibm.com nameserver = ns.almaden.ibm.com
ibm.com nameserver = internet-server.zurich.ibm.com
ns.watson.ibm.com internet address = 198.81.209.2
ns.austin.ibm.com internet address = 192.35.232.34
ns.almaden.ibm.com internet address = 198.4.83.35
internet-server.zurich.ibm.com internet address = 195.176.20.204
The mail exchange for ibm.com is ns.watson.ibm.com. It's address is 198.81.209.2.
Check out
Mr. DNS FAQ for mail questions. Great info in there and the one of the folks that wrote "DNS & Bind" answers most of the questions.