Reverse DNS question

I'm sure this has popped up before, but I've still to get my head around it :)

I have a server that serves both DNS, Web and Mail.

There is a separate IP address for 2 DNS servers and the web/mail.

Web/Mail : 12.34.56.78 DNS servers: 12.34.56.79 and 12.34.56.80

I have set up with my dedicated server hosting company a reverse IP of 78.56.34.12.in-addr.arpa domain name pointer server_host_name.mydomain.eu.

When I send an email out, the headers show:

Delivered-To: paul.pixel.co.uk@server_host_name.mydomain.eu Received: from [192.168.1.5] (82-46-6-144.cable.ubr04.aztw.blueyonder.co.uk [82.46.6.144]) by server_host_name.mydomain.eu (Postfix) with ESMTP id 90DC37700AD for paul@pixel.co.uk; Tue, 8 Dec 2009 21:59:41 +0000 (GMT)

and:

[~]$ host 12.34.56.78 78.56.34.12.in-addr.arpa domain name pointer server_host_name.mydomain.eu.

but I'm still getting this with one email address.: 550 Bad rDNS (in reply to MAIL FROM command)

Hotmail, GMail, Yahoo all work fine, but this one address (which goes via tidymail.co.uk) keeps rejecting my mail.

Anyone have some idea of what is incorrect here?

Thanks,

Paul