To look into this further I've just created a new email address for myself, added an email account using the shared server email settings for IMAP and SMTP and tried sending too emails to addresses they had trouble with yesterday.

One is rejected with:
host mta.xtra.co.nz [210.54.141.1]
SMTP error from remote mail server after initial connection:
421 Service not available: retry timeout exceeded

The second is rejected with:
host in-mig03.hes.trendmicro.com [54.219.191.101]
SMTP error from remote mail server after RCPT TO:<blah@blah.co.nz>:
550 5.7.1 <blah@blah.co.nz>: Recipient address rejected:
ERS-RBL.

The IP given in the headers for the second one is my IP address with blah.jetstream.xtra.co.nz.

Does this mean my IP is on a blacklist as well ?!?