MXToolbox is a great site for easily troubleshooting (some of) this stuff. Just type in the email host name (everything after the @ in the email address) and it'll show you who their MX server is. Then, click "SMTP Test" next to the result, and the site will automatically connect to their mail server to make sure it's up. If MXToolbox shows multiple MX servers, test them all in order.
If that passes, then you know the remote server is up, so that narrows down the problem to mail server configuration (either yours or theirs). You can use telnet to send an email manually through their server, and if it goes through, the problem is probably on your own server.
If you've never sent an email via telnet before, I recommend practicing on your own server first. Basically, you're going to telnet to port 25 on the SMTP server and type in commands, and the server will respond with numeric status codes and hopefully human-readable explanations, like this (your commands in bold, server responses in italics):
HELO myhostname.com
250 yourhostname.com Hello
MAIL FROM: me@myhostname.com
250 Sender ok
RCPT TO: you@yourhostname.com
250 recipient ok
DATA
250 enter your message
Subject: Test email
This is the body of the email. It ends when I type a period on a line by itself.
.
250 message sent
QUIT
220 Goodbye