When I first moved from a shared host to a dedicated server, and had my sites set up to send email (to customers), I immediately received rejections from Yahoo, Hotmail, AOL, and many other email servers (this was before there was Gmail). The rejections all shared the same reason. The IP block my server was in was blacklisted. That means that the IP address of my server was within a list of neighboring IP addresses that was blacklisted. It seems people grabbed dedicated servers and used them as spamming machines.
After attempting to communicate with these email services and get my IP whitelisted, I raised a ticket with my server host and they had a solution: smart host.
This smart host mechanism allows me to set my server to forward all outgoing mail to another server that only accepts from specified domains. Then it will send the email for me. Since the forwarding server is in a nice IP space, the email won't get bounced.
If you run into this problem and your server provider won't or can't do this for you, there is a very affordable service to do it for you.
I discovered this company around the same time I had the email issue, and ended up using them at a company I worked for that was running into a similar problem with their email campaigns (that were opt-in and on the "on the level"). It is what is called an SMTP relay. That means that you send email through them instead of directly into the wild.
The pricing is reasonable. If you're sending fewer than 1000 emails a month, you'll only pay $24 a year. I made that bold-faced so you'll notice. It's only $2 per month.
If you have a hosted email solution like Rackspace Mail, you can use them as your SMTP relay and save money. Since you would normally use their service to send mail from your mail client using SMTP (with authentication), you can use an SMTP library in your code (PHP, Perl, Ruby, Python, etc) to send mail. It's easy to set up and since you are using authentication in sending email, your mail provider can be assured it's you. Here's an example in PHP - note the SMTPAuth usage and username and password. Thereafter, you may completely remove sendmail and postfix from your server. There is no need for your server to act like a mail server at all. Like I mentioned long ago, that's a pain to manage on your own.
Next post: merchandising, merchandising, merchandising