Ongoing Problem: Transient parse errors

[Steve]

Hello!

I am having serious concerns with sendmail.

This "Transient parse error" problem has been occurring since the mid 90's
and I am still unable to find a solid answer to the problem!

The output of sendmail -q -v has many "Name server timeout
myaddress na domain.com... Transient parse error -- message queued for future
delivery" messages.

My resolv.conf is setup perfectly with two completely functional dns
servers.
NSLOOKUP for the MX records works instantly for ALL of the domains
listed below, Also, I can telnet to port 25 of the servers is responds with
(not that sendmail is trying to connect - having watched in verbose mode AND
in a protocol analyzer)

I am using 8.12.2 of sendmail, with almost all the defaults (no serious
changes).

Has anyone had similar problems?  Do you have the solution?! Please post for
all to see - share the wealth!


My MAILQ Outputs:

g1DIdCmw008297     8149 Wed Feb 13 13:39 <me na xxxxx.com>
      8BITMIME   (host map: lookup (interlink.net): deferred)
                                         <nileas na interlink.net>
g1DII8mw007526     8149 Wed Feb 13 13:18 <me na xxxxx.com>
      8BITMIME   (host map: lookup (gov.ab.ca): deferred)
                                         <anfduk na gov.ab.ca>
g1DIcjmw008282     8149 Wed Feb 13 13:38 <me na xxxxx.com>
      8BITMIME   (host map: lookup (allnet.on.ca): deferred)
                                         <mmvler na allnet.on.ca>
g1DJ81mw009351     8149 Wed Feb 13 14:08 <me na xxxxx.com>
      8BITMIME   (host map: lookup (perkins.ca): deferred)
                                         <cpagane na perkins.ca>
g1DIF3mw007418     8149 Wed Feb 13 13:15 <me na xxxxx.com>
      8BITMIME   (host map: lookup (nocdc.bc.ca): deferred)
                                         <jenifeerm na nocdc.bc.ca>
...................

THANKS,
  - Steve B.
    Canada