Unless the IP your VPS is sitting on has been blacklisted from a previous user, or your ISP is just plain evil, you should be fine sending out emails from a local SMTP server.
For maximum deliverability you will want to look at:
- Ensuring you have setup your SMTP server NOT to rely mail, and is safely behind a firewall. (this is a surefire way to get blacklisted within days)
- Ensure you have reverse-DNS setup for your VPS and that the host name your SMTP server is using matches your domain
- Adding SPF records for your domain.
- Checkout DKIM if possible.
Your AppEngine approach seems convoluted, if you wanted to use a third party system something like SendGrid would be a better fit.