Mail stuck in queue - connection refused?

Check again that your IP address is not blacklisted. Mail servers are configured with different RBL providers:

http://multirbl.valli.org/

Definitely not on any blacklists. It's a very strange problem.

We are also encountering other issues which seem a little strange with it.

For instance:

2016-04-26 14:03:38 SMTP error from remote mail server after RCPT TO:<joe.bloggs@remote.maildomain.uk>: host host remote.mail.server [123.62.5.172]: 550 Your mail account has been blacklisted from sending e-mails. KB17293
2016-04-26 14:03:38 joe.bloggs@remote.maildomain.uk P=<joe.bloggs@remote.maildomain.uk> R=dnslookup T=remote_smtp: SMTP error from remote mail server after RCPT TO:<joe.bloggs@remote.maildomain.uk>: host remote.mail.server [123.62.5.172]: 550 Your mail account has been blacklisted from sending e-mails. KB17293

Which is strange because we aren't blacklisted and we can send mail from others internal users to the other domain

Our setup is:
Incoming: INTERNET > UTM SMTP Proxy > EXCHANGE
Outgoing: EXCHANGE Send connector > UTM SMTP Proxy > INTERNET

Mail to most (not all) other domains flows fine (in & out)

Another thing we have noticed is we have a distribution group on exchange eg xxx@yyy.com
That distribution group has 4 internal recipients & 4 external recipients.
When we use an internal address, mail goes out to everybody in that distribution group.
When we use an external address to mail that distribution group, mail only goes to the internal users and the external users get bounced at the UTM

Exchange does its part and sends to all but the UTM seems to bounce the external mail due to it coming from an external contact?

Are the "problem" domains perhaps using greylisting?

Cheers - Bob

Not sure at this point in time.

R=dnslookup T=remote_smtp defer (111): Connection refused

With the above, can you explain what this means as it's a bit vague.

R=dnslookup   = what does this mean? Does it mean that the DNS lookup was successful? It's very vague
T=remote_smtp defer (111): Connection refused  = Is this message from the UTM itself and formatted as such? 

And another separate issue: 

T=remote_smtp: SMTP error from remote mail server after RCPT TO:<joe.bloggs@remote.maildomain.uk>: host remote.mail.server [123.62.5.172]: 550 Your mail account has been blacklisted from sending e-mails. KB17293

Is the above message formatted from the UTM or is it a direct message from the remote server?

Think I might have to turn the debug messages on although that would have been a handy feature in the GUI also.

ummmmmhhhh

Finally solved. It seems i had set some country blocking on the firewall.

And although I was sending to only .uk addresses, their cloud mail servers were in various places that I'd blocked at the firewall.

Turning Country blocking off resolved this. One to look out for in the future.

I would only block inbound, not outbound traffic.  To maintain inbound Country Blocking in this situation, make an Exception for SMTP traffic.  If you can limit the Exception to select countries or even specific IPs/subnets, all the better.

Cheers - Bob

Today I had exactly the same problem and found this old thread.

Turned out that one of our suppliers is using a mail provider with 62.x.x.x addresses, which were blocked by "country blocking".

My exception now excludes outgoing SMTP-traffic for all countries and everything is working fine since then.

Thanks Bob for your suggestion!