Cant Send Mails To Hotmail, Even With A SPF Record

I have 1 site on a dedicated server, this site can send mails to any server in the world, except to hotmail... I dont know why, each time we try to send a mail using a PHP Script (using nobody as user, as you can see in the code below) the server rejects the email sent to hotmail, this is the error:

Code:
2007-09-08 21:24:13 1IUCT7-0004BE-7A ** destinationuser@hotmail.com R=lookuphost T=remote_smtp: SMTP error from remote mail server after MAIL
FROM:<nobody@server.theserver.com> SIZE=31435: host mx4.hotmail.com [65.54.244.232]: 550 Your e-mail was rejected for policy reasons on this gateway.
Reasons for rejection may be related to content with spam-like characteristics or IP/domain reputation problems.

If you are not an e-mail/network admin please contact your E-mail/Internet Service Provider for help.

For e-mail delivery information, please go to http://postmaster.live.com

I checked and the server IP is not listed at any SPAM list, also domain has an SPF record that is configured like this:

Code:
domain.com. 14400 IN MX 10 mail.domain.com.

mail 14400 IN A 89.XX.XX.XX
www 14400 IN A 89.XX.XX.XX
ftp 14400 IN A 89.XX.XX.XX
server 14400 IN A 89.XX.XX.XX
domain.com. IN TXT "v=spf1 ip4:89.XX.XX.XX a mx a:mail.domain.com ~all"
Is the SPF record well configured?, and the MX record, i think its OK... never had issues with this kind of config on normal sites..

Just in case it helps, at /etc/localdomains i have 2 sites, the server hostname and the site domain.com.

Im using RHES 4 + cPanel 11.