Sendmail getting the error "Name server timeout"

Issue

• We experience delay in our mail server
• Some of our email is going directly to the waiting queue
• We can see the following error in the /var/log/maillog.

Jul  2 10:03:09 myserver sendmail[31185]: s62228of031185: --- 451 google.com: Name server timeout
Jul  2 10:03:09 myserver sendmail[31185]: s62228of031185: --- 050 <user@go0gle.com>... Transient parse error -- message queued for future delivery