Sendmail/'host name lookup failure'

[Jeff Gentry]

Hello ...

The other day I rebooted my FreeBSD machine.  Ever since then, messages to
hotmail.com and yahoogroups.com are not going through - the mail logs
report that there is a 'host name lookup failure' to the specific MX
hosts (eg 'mx1.hotmail.com').  The thing is though, I can run dig/nslookup
on these hotsnames perfectly fine - in fact I can even telnet to port
25 of all of these hostnames, issue a HELO, etc.

Does anyone have an idea what might be going on here?