I would try to make sure that the email address you are using to send from (i.e. email@example.com) matches the domain name (i.e. domain.com) of the Magento site.
If you’re trying to send from a yahoo, hotmail, gmail or other web-based email address, most spam filters will reject this when it’s sent.
I’d also make sure that you have a valid PTR record for the IP address of the server, using a domain name that matches the name of the site; also add in an SPF record that allows the server to send out mail on behalf of the organization.
Oh, make sure the IP address of the server isn’t blacklisted, too… (do a quick search to find a site that will do this).
Most email from Magento is sent out via SendMail, so I would also check with you hosting company as well.
Hope this helps!