I'm running redhat 9 / sendmail. I have sendmail working for incoming mail perfectly for all four of my domains. Any e-mail sent to any of the four domains is correctly and quickly delivered to the correct mail boxes.

My problem is outgoing mail. Out going mail is getting stuck in my mail queue. For example, if I try to send mail to jsolis@outsidedomain.com, sendmail -q -v reports the following:

Running /var/spool/mqueue/h7KL6MN2001696 (sequence 10 of 12)
outsidedomain.com: Name server timeout
<jsolis@outsidedomain.com>... Transient parse error -- message queued for future delivery

DNS resolution on this box is otherwise healthy.

Also, MX records on "outsidedomain.com" is setup properly too. I've been receiving mail at that address for years now and a dig reports the MX records properly. Name server timeout's also occur for yahoo.com addresses, so it's not a problem on that end.

Since there are still no replies to my posting, I figured I would post my solution to this problem. I installed the latest version of postfix =P

Figured it was more secure anyhow. And the fact that it actually sent my mail out was a big plus.