OS type: UNIX or Windows Mail server - are you using sendmail Do you host your own DNS Have you checked your mail logs Can you send email to yourself - local email
I had a similar problem with my FreeBSD, Sendmail setup. I have DSL service and was able to send email from my server (hosting geeklog) to my internal domain but not externally. I was getting DNS errors in my sendmail logs.
My ISP was not letting the mail out - spam policy about other smtp servers within their network. I configured my sendmail to use the ISP's smart SMTP host, restarted the sendmail process and all my mail that was hung up went out - problem solved.
Blaine