Можно попробовать использовать smtp провайдера. их сейчас много. mailgun, sendgrid, smtp.com. У первого free account до 200 или 300 сообщений в сутки, зато очень богатые API
Лично я использую собственный SMTP сервер (postfix), с spf, dkim, whitelisting у major ESP (yahoo, google, aol, roadrunner). Почта уходит быстро, попадает в инбокс. Наверное в случае с VDS без выделенного IP этот вариант не пройдет.
