have a reverse but still getting problems with reverse DNS pointing to unknown hostname-Collection of common programming errors

I am having problems sending email from a domain I host myself.

I have omitted the actual ip address in question, I am not sure how secure it is that I post it. However the problem is as follows:

According to my ISP the reverse was done for the my IP to point to the FQDN taht follows.

(XXX.XXX.XXX.XXX) -> mymachine.domain.com

However I still get email undelivered:

host inc.wanadoo.es[xxx.xxx.xxx.xxx] refused to talk to me: 550 Reverse DNS lookup failed for host xxx.xxx.xxx.xxx.

and upon testing I get the following error:

Reverse for xxx.xxx.xxx.xxx points to an unknown host name (mymachine.mydomain.com).

The weirdest, perhaps, is that using some tools (i.e mxtoolbox) to check that the rDNS agrees to my SMTP banner, all checks fine, however, it fails when I use other tools.

What can be the error?

Do I need a reverse for every single domain I host or is it enough with the one for the mail server?

Bluetxxth

Ubuntu Server 10.04. LTS

Bind9

Postfix version 2.x.x

Edit: In trying what you suggested I received the following:

first test

host -t a neo001.neoclash.com 8.8.8.8

mymachine.mydomain.com 8.8.8.8 Using domain server: Name: 8.8.8.8 Address: 8.8.8.8#53 Aliases:

Host mymachine.mydomain.com not found: 3(NXDOMAIN)

second test

host -t ptr 1.2.3.4.in-addr.arpa 8.8.8.8

host -t ptr 109.124.134.63.in-addr.arpa 8.8.8.8 Using domain server: Name: 8.8.8.8 Address: 8.8.8.8#53 Aliases:

Host 1.2.3.4.in-addr.arpa not found: 3(NXDOMAIN)

zone configuration

$TTL 12H
$ORIGIN mydomain.com.

enter@  IN  SOA ns1.mydomain.com. postmaster.mydomain.com. (
        2011030805
        8H
        2H
        7D
        1D )
            IN              NS              ns1.mydomain.com.
            IN              NS              ns2.mydomain.com.
            IN              MX      10      mail.mydomain.com.
            IN              MX      20      mail.anotherdomain.net.

mydomain.com. IN A 1.2.3.4

www IN A 1.2.3.4

mydomain.com. IN TXT "v=spf1 a mx ip4:1.2.3.4 ip4:1.2.3.4 ~all"

localhost IN A 127.0.0.1

mail IN A 1.2.3.4
mail IN A 1.2.3.5
ns1 IN A 1.2.3.4
ns2 IN A 1.2.3.5