The correct name of the mail server and it's IP address.
Lines from sendmail.cf which mention the mail server by name and/or by IP address.
Lines from /etc/hosts which mention the mail server by name and/or by IP address.
The output from "nslookup" both by name and by IP address.
The contents of /etc/resolv.conf
The contents of /etc/nsswitch.conf
As TonyFullerManv deduced. Please post the output from the failing "ping" command.