"Temporary failure in name resolution" or "Host name lookup failure" only for some domains but not others

Issue

• Temporary failure in name resolution or Host name lookup failure only for some domains but not others
• The problem only occurs on RHEL6, not on RHEL5 or Solaris
• The problem can be seen with telnet and with traceroute on RHEL6
• Specific DNS query tools/utilities such as host or nslookup or dig work fine in all environments

# cat /etc/redhat-release
Red Hat Enterprise Linux Server release 6.7 (Santiago)

# telnet host.example.com
telnet: host.example.com: Temporary failure in name resolution
host.example.com: Host name lookup failure

# cat /etc/redhat-release
Red Hat Enterprise Linux Server release 5.11 (Tikanga)

# telnet host.example.com
Trying 10.0.0.157...
Connected to host.example.com.
Escape character is '^]'.