Use telnet to check your mail server connectivity

Perform a telnet to port 25 on the remote domains mail server, it usually gives an indication of why you cannot send to them.

1. Go to start run, type cmd ok
2. nslookup -type=mx theirdomain.com

note the fqdn of their mail server

telnet fqdnoftheirmailserver 25 (hit enter)
mail from:you@yourdomain.com (hit enter)
rcpt to:them@theirdomain.com (hit enter)
data (hit enter)
. (hit enter)
. (hit enter)

Should say message was queued.