A menos que o IP em que o seu VPS está hospedado tenha sido colocado na lista negra de um usuário anterior, ou o seu ISP seja simplesmente maligno, você deve estar bem enviando e-mails de um servidor SMTP local.
Para máxima capacidade de entrega, você vai querer olhar:
- Garantir que você tenha configurado seu servidor SMTP NÃO para confiar em e-mails e esteja protegido por um firewall com segurança. (esta é uma maneira infalível de entrar na lista negra dentro de alguns dias)
- Verifique se você tem a configuração de DNS reverso para seu VPS e se o nome do host que seu servidor SMTP está usando corresponde ao seu domínio
- Adicionando registros SPF ao seu domínio.
- Checkout DKIM se possível.
Sua abordagem do AppEngine parece confusa, se você quiser usar um sistema de terceiros, algo como SendGrid seria mais adequado.