What port are you using to send email? (Your settings should tell you)

More and more connectivity providers have now started blocking Port 25 traffic (which is the port used for non-secure connections and for TLS)

My company server uses SSL (Port 465) which usually gets round the problem (In other words, I've never had Port 465 traffic blocked)