SMTP problems: Host not found, try again

[david-8uUts6sDVDvs2Lz0fTdYFQ at public.gmane.org]

So I'm kinda sorta close to finishing my server rebuild, but I'm still
having issues.  One I would like to get solved asap is this SMTP issue. 
This is Ubuntu Jaunty with postfix/dovecot.

I see messages like this very frequently (email addresses redacted) in the
logs and the output of postqueue -p:
813404C5F7     2130 Tue Jun  2 03:47:36 
particularization9-qIPW8QmpbdTTeotY1rLAZGXnswh1EIUO at public.gmane.org
(delivery temporarily suspended: Host or domain name not found. Name
service error for name=comcast.net type=MX: Host not found, try again)
                                         XXXXX-Wuw85uim5zDR7s880joybQ at public.gmane.org

809EE461A7     8687 Mon Jun  1 12:05:35  avengesp616-sdv56KyyKd+sTnJN9+BGXg at public.gmane.org
(delivery temporarily suspended: Host or domain name not found. Name
service error for name=acm.org type=MX: Host not found, try again)
                                         XXXXX-HInyCGIudOg at public.gmane.org

and a bunch of other domains.

"digg acm.org mx" returns the list of MX servers.
I can telnet to one or more of the XM servers on port 25.