Message rejected при отправке скриптом через SMTP для аккаунта Google Apps. ЧЯДНТ?
Ну во-первых, у гуглопочты есть лимит сообщений, если мне не изменяет память, где-то 5000/сутки.
Во-вторых, что мешает нанять сисадмина за небольшую копеечку, чтобы он правильно настроил вам почтовик, раз уж есть где, и вы не уверены в своих силах?

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