I can't send email from my server to gmail addresses
I'm not sure if this is your exact problem, but I experienced something similar, and in my case I was able to solve it by setting up a Reverse DNS entry for my mail server's IP. That way a receiving SMTP server can verify that a message sent from your server's IP can be resolved to the same domain name as the "From" address in the SMTP header. (I could be wrong on some of the details.)
Google seems particularly picky about that, even if you've also set up SPF and DomainKeys.