Lots of major ISP (Internet Service Provider)s block outbound TCP (Transmission Control Protocol) port 25. Don't you support Port 587 (the message submission port)?
“Customer in a support ticket”
Really?
Oh … um … looky there (Message Submission) [1].
Basically, it's running a restricted version of SMTP (Simple Mail Transport Protocol) over port 587 and from what I can find, it's only been in the last two years or so has it been widely implemented, although this is the first I've heard of it.
Interesting. Looks like I'll be reading up on this.