554 – Sending MTA’s poor reputation

I am running an email server on 77.245.64.44 and have recently started to have problems with remote delivery of emails sent using this server. Only about 5% of recipients are rejecting the emails, but they all share the following common message…

Remote host said: 554 Your access to this mail system has been rejected due to the sending MTA's poor reputation.

As far as I can tell my server is not on any blacklists, and it is set up correctly (the reverse DNS checks out and so on). I'm not even sure what the "Sending MTA" is, but I assume it's my server.

If anyone could shed any light on this I'd really appreciate it!

Here's the full bounce message…

Could not deliver message to the following recipient(s):

Failed Recipient: somebody@sunday-times.co.uk
Reason: Remote host said: 554 Your access to this mail system has been rejected due to the sending MTA's poor reputation. If you believe that this failure is in error, please contact the intended recipient via alternate means.

   -- The header and top 20 lines of the message follows --

Received: from 79-79-156-160.dynamic.dsl.as9105.com [79.79.156.160] by mail.fruityemail.com with SMTP;
   Thu, 3 Sep 2009 18:15:44 +0100
From: "Phil Wilks" 
To: 
Subject: Test 
Date: Thu, 3 Sep 2009 18:16:10 +0100
Organization: Fruity Solutions
Message-ID: 
MIME-Version: 1.0
Content-Type: multipart/alternative;
    boundary="----=_NextPart_000_01C2_01CA2CC2.9D9585A0"
X-Mailer: Microsoft Office Outlook 12.0
Thread-Index: Acosujo9LId787jBSpS3xifcdmCF5Q==
Content-Language: en-gb
x-cr-hashedpuzzle: ADYN AzTI BO8c BsNW Cqg/ D10y E0H4 GYjP HZkV Hc9t ICru JPj7 Jd7O Jo7Q JtF2 KVjt;1;YwBoAGEAcgBsAG8AdAB0AGUALgBoAHUAbgB0AC0AZwByAHUAYgBiAGUAQABzAHUAbgBkAGEAeQAtAHQAaQBtAGUAcwAuAGMAbwAuAHUAawA=;Sosha1_v1;7;{F78BB28B-407A-4F86-A12E-7858EB212295};cABoAGkAbABAAGYAcgB1AGkAdAB5AHMAbwBsAHUAdABpAG8AbgBzAC4AYwBvAG0A;Thu, 03 Sep 2009 17:16:08 GMT;VABlAHMAdAA=
x-cr-puzzleid: {F78BB28B-407A-4F86-A12E-7858EB212295}

This is a multipart message in MIME format.

------=_NextPart_000_01C2_01CA2CC2.9D9585A0
Content-Type: text/plain;
    charset="us-ascii"
Content-Transfer-Encoding: 7bit