Most mail failures blamed on Magento are actually Server Admin 101 setup problems and outside the venue of this section of Stack Exchange. It sounds like you will need to set up Postfix. At one time there was a Wiki over on MagentoCommerce.com giving instruction on how to do this, but it seems to have eBayvaporated.
The rest are because the old Port 25 MX pump'n dump is viewed as a spam source and the remote server is rejecting unauthenticated, plaintext transmitted email from a server that fails to use mechanisms like SPF or DKIM and reverse lookup records.
Get yourself an email service provider like Rackspace and an authorized SMTP module like Ashley Shroeder's SMTP Pro which allows you to send SSL/TLS protected email to an authenticated SMTP server. Check with your hosting provider to see if they do authenticated, secured mail transport if you don't want to use an external email service provider, some are getting smart about extending the value of their services. Also set up SPF records in your DNS.
Failing to set up an authenticated, secured mail service can also result in email scoring that dumps all your transactional emails into the corporate spam quarantine, people's personal quarantine and/or local email client spam folders.