What hosting are you using?

I use Linode, and you need a support ticket (and rDNS set up) for Linode to open port 25.