Mails were being bounced due to CBLs HELO check.

URL: http://cbl.abuseat.org/helocheck.html

It turned out that when Plesk was installed it was installed with the hostname localhost.localdomain (ie. domain not changed at all).  In the Plesk control panel the hostname had been updated, however, the qmail server was still presenting itself as localhost.localdomain.

It turns out that in the file: /var/qmail/control/me

It had localhost.localdomain and wasn’t updated.  Manually updating this and restarting qmail resolved the issue.