It appears that our firewall is not allowing connection to outside MX hosts. I think I need to configure sendmail to forward emails to our local smtp host, but I am not sure how to do that.
Best to do that anyway. Some e-mail providers will only accept e-mail from known mail servers (AOL) and bounce if the IP of your sending server is not a static, known mailserver.
What you want is 'SMARTHOST'.
DSmy.mail.server.com in sendmail.cf
or
define(`SMART_HOST', `my.mail.server.com')dnl in sendmail.mc