I seem to recall that some mail servers will not accept outgoing mail from other domains. I presume this is a spamming issue.
So if you are sending e-mail to your usual SMTP server but through a different ISP, it may be rejected.
I can't recall, but it may be possible to send to your usual email server if you include outgoing mail authentication.
Sorry this is a bit vague - I am not an expert on email, but it might give you something to explore further.