Status_203 - 8:35 am on Sep 15, 2011 (gmt 0)
Actually the mail in question is mission-critical for the normal functioning of my app
Do you have DomainKeys set up?
I recently added a forum to one of my domains (mostly to handle user registrations for tools on the site rather than for the forum itself) but it soon became clear that despite correct SPF and reverse DNS having been setup, certain email providers (including Yahoo) were bouncing mails from the server. Investigation indicated that lack of DomainKeys was the issue.
After a few searches I decided life was too short to include setting up DomainKeys on my current server and went with a third party, self-service, cloud based emailer ($0.001 per email - at my volumes $20 will last all year, maybe more :( ). Note if you're using PHP then the PEAR Mail package allows sending through 3rd party SMTP servers.