sendmail won't use relay

[The Derfer]

A RHEL5 client set up properly to send to another host as
a relay doesn't do it. Yes, the "DS" field is set up in sendmail.cf,
sendmail daemon restarted a million times, etc etc.
Everything looks fine, it just doesn't work.
Why does it try to send the mail itself? Shouldn't even attempt
a DNS lookup. The mailhost (relay) can do that but here, the
client tries to do it itself for some reason. Please advise.
I try sending a test
to see if this is working and here's what I get:

root@e1198pdb3 ~# sendmail -v -d8.99 -d38.99 the...@gmail.com
openmap() dequote:dequote NULL: valid
openmap() host:host NULL: valid
getcanonname(gmail.com), trying dns
dns_getcanonname(gmail.com, trymx=1)
dns_getcanonname: trying gmail.com. (AAAA)
NO: errno=111, h_errno=2
dns_getcanonname: trying gmail.com. (A)
NO: errno=111, h_errno=2
dns_getcanonname: trying gmail.com. (MX)
NO: errno=111, h_errno=2
dns_getcanonname: trying gmail.com. (AAAA)
NO: errno=111, h_errno=2
dns_getcanonname: trying gmail.com. (A)
NO: errno=111, h_errno=2
dns_getcanonname: trying gmail.com. (MX)
NO: errno=111, h_errno=2
getcanonname(gmail.com), trying files
text_getcanonname(gmail.com)
getcanonname(gmail.com), failed, status=68
gmail.com: Name server timeout
derf...@gmail.com... Transient parse error -- message queued for
future delivery
closemaps: closing host (NULL)
closemaps: closing dequote (NULL)