For a web application I'm working on right now it's very important that automated e-mails arrive at the recipient. I've set up the mail server on the VPS that the application is going to run on. I've taken all the regular precautions to make sure that the e-mails it sends are not going to be filtered out: SPF, DKIM, e-mails have both a plain text and html part, html part is valid html etc. etc.
Still some services - in particular Microsofts outlook.net addresses - either block the message or automatically mark it as junk mail. I've read up a little on how Microsoft determines if a message is junk and in our case it's most likely the reputation of the mail server. Since it's a new server it doesn't have any reputation yet.
How do other developers deal with this type of problem? Do you use external SMTP services like Google Apps to send mail from your application? Any ideas or tips?