I've used the Ansible playbook on two Linode servers running Ubuntu 18.04 LTS, the main difference between them being that one is for Plone 4.3.19 and the other for Plone 5.2.1.
The Plone site on the former is able to send email via Mailgun (telnet smtp.mailgun.org 587)
# telnet smtp.mailgun.org 587
Trying 52.34.221.85...
Connected to smtp.mailgun.org.
Escape character is '^]'.
220 Mailgun Influx ready
but the latter is not (!). I am puzzled why there would be this difference...
Interesting. Outbound port 587 is pretty standard for SSL SMTP, but Mailgun will let you use other ports.
Our servers listen on ports 25, 587, and 465 (SSL/TLS)
I tried this Stack Overflow answer. Changing to use port 2525 worked! (even though I am using Linode.com, not Google) (and yeah it never occurred to me to try 25 because it's usually for plaintext SMTP or 465 because I thought that the Linode's IP was blocked, not a specific inbound port).
Google Compute Engine does not allow outbound connections on ports 25, 465, and 587. By default, these outbound SMTP ports are blocked because of the large amount of abuse these ports are susceptible to.
Port 25 outbound is blocked on Google Cloud. Mailgun mirrors 587, on port 2525 - so try using port 2525.
As a quick test you could also try telnetting from the command line to check connectivity, like this:
> telnet smtp.mailgun.org 2525