Sendmail error delaying relay

When I try to send mail, sendmail delays a lot. After monitoring syslog, I noticed that sendmail starts with this first message... waits a minute and gives the second message... waits another minute and then sends off the email. How do I correct this in sendmail or completly disable it. I'm sending to an Open-Relay circuit and after sendmail sends it, it works fine.

Mar 15 03:38:16 solaris-host sendmail[781]: [ID 702911 mail.crit] My unqualified host name (localhost) unknown; sleeping for retry
Mar 15 03:39:16 solaris-host sendmail[781]: [ID 702911 mail.alert] unable to qualify my own domain name (localhost) -- using short name

hostname;domainname displays proper hostnames and domainnames so I don't think this is a problem that is related to /etc/hosts.

any ideas?
Thanks!

---------- Post updated 03-15-10 at 12:16 AM ---------- Previous update was 03-14-10 at 11:32 PM ----------

There were issues regarding /etc/host and /etc/inet/ipnodes. They somehow got unlinked and no longer matched. I corrected the problem, the errors went away and sendmail was no longer delayed. Thanks all.