Чтобы отправлять почту в свои домены Google Apps через sendmail , см. Этот ответ . Это может не решить вашу проблему, поскольку IP-адрес вашего VPS может иметь «плохую» репутацию по отправке по какой-либо причине. Вы можете попробовать и проверить репутацию своих адресов в таких сервисах, как:
и во множестве существующих там DNSBL.