i have problems with my sendmail also;
just a short while ago, cox (cable modem provider) must have switched it's dhcpc server release info, because it no longer returns my psuedo fqdn when i announce that my host is "dAn" (it used to spit back "dAn.hr.cox.net").... sendmail tries for a minute and a half (sometimes longer) to resolve my hostname "dAn" but to no avail.... let it run and check your logs.
I have since stopped the sendmail daemons from executing at startup because I am too lazy to use my ip as my hostname or register a valid one.... or figure out how to get sendmail to stop checking this.... anyway.
if this helps you, let me know.
-t.