Some users are trying to send email to certain domains using Exchange Server 2003, but the message is always is rejected and the following message is shown:

5.5.0 smtp;554 Transaction Failed Spam Message not queued

The IP is not in a black list (checked using http://whatismyipaddress.com/blacklist-check and is clean - not listed).

The emails were checked using using smtpdiag ("a troubleshooting tool designed to work directly on a Windows server with IIS/SMTP service enabled or with Exchange Server installed") and the connection using port 25 is ok.

Also, an nslookup with set type=ptr shows (names and IP changed, ">" means I typed something):

C:\Documents and Settings\administrator>nslookup
Default Server: publicdns.isp.net
Address: 10.10.10.10

> server publicdns.isp.net
Default Server: publicdns.isp.net
Address: 10.10.10.10

> set type=ptr

>mydomain.com

Server: publicdns.isp.net
Address: 10.10.10.10

mydomain.com
primary name server = publicdns.isp.net
responsible mail addr = root.isp.net
serial = 2011061301
refresh = 10800 (3 hours)
retry = 3600 (1 hour)
expire = 604800 (7 days)
default TTL = 86400 (1 day)
> 20.21.22.23
Server: publicdns.isp.net
Address: 10.10.10.10

23.22.21.20.in-addr.arpa name = mail.mydomain.com
20.21.in-addr.arpa nameserver = publicdns.isp.net
20.21.in-addr.arpa nameserver = publicdns2.isp.net
publicdns2.isp.net internet address = 10.10.10.11
publicdns.isp.net internet address = 10.10.10.10

Server: publicdns.isp.net
Address: 10.10.10.10

23.22.21.20.in-addr.arpa name = mail.mydomain.com
20.21.in-addr.arpa nameserver = publicdns.isp.net
20.21.in-addr.arpa nameserver = publicdns2.isp.net
publicdns2.isp.net internet address = 10.10.10.11
publicdns.isp.net internet address = 10.10.10.10
> set type=mx
> mydomain.com
Server: publicdns.isp.net
Address: 10.10.10.10

mydomain.com MX preference = 10, mail exchanger = mail.mydomain.com
mydomain.com nameserver = publicdns.isp.net
mydomain.com nameserver = publicdns2.isp.net
mail.mydomain.com internet address = 20.21.22.23
publicdns2.isp.net internet address = 10.10.10.11
publicdns.isp.net internet address = 10.10.10.10
> set type=a
> mydomain.com
Server: publicdns.isp.net
Address: 10.10.10.10

Nombre: mydomain.com
Address: 20.21.22.23

When I test the spf record with http://www.mxtoolbox.com it shows:

TXT mydomain.com 24 hrs v=spf1 a mx ptr ip4:20.21.22.23 mx:mail.mydomain.com -all

Any clues of what's happening here?