OS: Fedora Core 3

I have a webserver inwhich I send email out using PHP and (I believe) sendmail. I use the mail function in PHP. The function works fine when emailing to Gmail and Hotmail, but if I try to send an email to a server who uses grey listing the email never goes through. I'm figuring that I need to change a setting to tell my server to confirm delivery so that it will retry sending the message.

Things I've tried:

- I opened port 25 on my router and firewall

Other than that I'm not sure where else to start. Thanks for your advice.

-Mark.