Emails being marked as spam on new server for no apparent reason

I recur to you in desperation because I've been pulling my hair off for two days but Gmail, Hotmail and Yahoo seems to hate me no matter what. Here is the thing:

- Domain has a valid PTR (rDNS).
- Domain has a static IP for its SSL certificate.
- Mail headers are properly configured, set by CodeIgniter.
- Test mail scripts work fine on other servers, but are marked as spam on this one.
- Domain has a valid SPF record.
- Domain is based on Google Apps MX records.
- This is a brand new dedicated server, based on EXIM and WHM.

The messages sent from this server (from PHP) are always marked as spam on Gmail, Hotmail and Yahoo. I don't think headers are the problem, because the same scripts on other servers work perfectly and arrive at the inbox.

Take a look and please let me know what you guys think. I'd really appreciate your input.

Thanks in advance!