My anecdotal evidence is that simple postfix setup with IP from a reputable hoster which is not blacklisted works perfectly. And it's actually pretty simple to configure postfix for sending mail (now configuring postfix + dovecot + auth + spam filtering is another story).