Have a look in your maillog (in RedHat and Fedora distros this is in /var/log). It shows details of all sendmail transactions. It may give you more of an idea what is wrong.
It will show you the mail relays that messages are going through, and you could try pinging them to see if their names are resolved by DNS.
Also try a ping to www.google.com
to see if DNS resolves that - maybe you have a general DNS problem rather than just a mail problem.