Postfix – can send mail to outside directly from server, but not from remote hosts connecting to it

I'm currently in the process of configuring a mail server on our AWS VPC to relay messages from applications on multiple servers on that same network onto the internet. This SMTP server is only ever meant to send automated emails and never to receive anything. The main purpose of this machine is to monitor and centralize logs, but I've been asked to configure it as a mail server as well.

So far, I've been able to configure postfix to enable sending email to my work email address from the command line (using the mail command) and email alerts from the log manager.

However, I've attempted to connect to this SMTP server from the other machines through telnet and I'm unable to send email – logs show a message from google alerting that mail from the server's public IP address is rate limited due to low reputation.

This seems odd to me because, in both situations, the emails are coming from the same public ip address.

Log entries for a successful email look something like this:

host.sub.example.com postfix/pickup[23352]: D1F941407D1: uid=1001 from=<user@host.sub.example.com>
host.sub.example.com postfix/cleanup[26119]: D1F941407D1: message-id=<20170130114758.D1F941407D1@mail.example.com>
host.sub.example.com postfix/qmgr[23353]: D1F941407D1: from=<user@host.sub.example.com>, size=384, nrcpt=1 (queue active)
host.sub.example.com postfix/smtp[26122]: D1F941407D1: to=<work.email@example.com>, relay=alt2.aspmx.l.google.com[74.125.205.27]:25, delay=0.81, delays=0.01/0/0.32/0.47, dsn=2.0.0, status=sent (250 2.0.0 OK 1485776921 14si8136222lju.15 - gsmtp)
host.sub.example.com postfix/qmgr[23353]: D1F941407D1: removed

Generated by the command: echo "test" | mail -s "testsubj" work.email@example.com

Unsuccessful ones look like this:

host.sub.example.com postfix/smtpd[26773]: connect from otherhostname[private-ip-address]
host.sub.example.com postfix/smtpd[26773]: improper command pipelining after MAIL from otherhostname[privateipaddress]: RCPT TO: work.email@example.com\r\nDATA\r\nFrom: fromheader@mail.example.com\r\nSubject: word1 word2\r
host.sub.example.com postfix/smtpd[26773]: ADD161407D1: client=otherhostname[private-ip-address]
host.sub.example.com postfix/cleanup[26780]: ADD161407D1: message-id=<>
host.sub.example.com postfix/qmgr[23353]: ADD161407D1: from=<mailfrom@mail.example.com>, size=284, nrcpt=1 (queue active)
host.sub.example.com postfix/smtp[26781]: ADD161407D1: host alt1.aspmx.l.google.com[173.194.69.26] said: 421-4.7.0 [public-ip-address      15] Our system has detected that this message is 421-4.7.0 suspicious due to the very low reputation of the sending IP address. 421-4.7.0 To protect our users from spam, mail sent from your IP address has 421-4.7.0 been temporarily rate limited. Please visit 421 4.7.0  https://support.google.com/mail/answer/188131 for more information. 28si16209237wru.213 - gsmtp (in reply to end of DATA command)
host.sub.example.com postfix/smtpd[26773]: disconnect from otherhostname[private-ip-address]
host.sub.example.com postfix/smtp[26781]: ADD161407D1: to=<work.email@example.com>, relay=alt2.aspmx.l.google.com[74.125.205.26]:25, delay=16, delays=0.02/0/16/0.31, dsn=4.7.0, status=deferred (host alt2.aspmx.l.google.com[74.125.205.26] said: 421-4.7.0 [public-ip-address      15] Our system has detected that this message is 421-4.7.0 suspicious due to the very low reputation of the sending IP address. 421-4.7.0 To protect our users from spam, mail sent from your IP address has 421-4.7.0 been temporarily rate limited. Please visit 421 4.7.0  https://support.google.com/mail/answer/188131 for more information. 65si8149735lfw.365 - gsmtp (in reply to end of DATA command))

Generated by the following telnet exchange:

Trying private-ip-address...
Connected to private-ip-address.
Escape character is '^]'.
220 mail.example.com ESMTP Postfix (Ubuntu)
HELO mail.example.com       
MAIL FROM: mailfrom@mail.example.com
RCPT TO: work.email@example.com
DATA
From: fromheader@mail.example.com
Subject: word1 word2
Line1
Line2
Line3
.
250 mail.example.com
250 2.1.0 Ok
250 2.1.5 Ok
354 End data with <CR><LF>.<CR><LF>
250 2.0.0 Ok: queued as ADD161407D1
QUIT
221 2.0.0 Bye
Connection closed by foreign host.

For completeness' sake this is my current configuration, using mostly default values:

smtpd_banner = $myhostname ESMTP $mail_name (Ubuntu)
biff = no
append_dot_mydomain = no
readme_directory = no

smtpd_tls_cert_file=/etc/ssl/certs/ssl-cert-snakeoil.pem
smtpd_tls_key_file=/etc/ssl/private/ssl-cert-snakeoil.key
smtpd_use_tls=yes
smtpd_tls_session_cache_database = btree:${data_directory}/smtpd_scache
smtp_tls_session_cache_database = btree:${data_directory}/smtp_scache

smtpd_relay_restrictions = permit_mynetworks permit_sasl_authenticated defer_unauth_destination
myhostname = mail.example.com
alias_maps = hash:/etc/aliases
alias_database = hash:/etc/aliases
mydomain = mail.example.com
myorigin = /etc/mailname
mydestination = mail.example.com localhost
relayhost =
mynetworks = 127.0.0.0/8 [::ffff:127.0.0.0]/104 [::1]/128 private-ip-network
mailbox_size_limit = 0
recipient_delimiter = +
inet_interfaces = all 
inet_protocols = ipv4
smtp_generic_maps = hash:/etc/postfix/generic

Questions:

Why can I send mail locally from the SMTP server, but not from hosts connecting remotely to it?

Could it have something to do with reverse DNS or SPF records? If so, why aren't all emails blocked?

Could it have to do with the fact that I haven't configured authentication yet?

I hope I'm not overlooking something completely obvious. I barely have any experience with mail servers and I've only ever done anything slightly related in a small project at school using postfix+dovecot and local users.

Thank you very much for taking the time to read this, and I apologize if I've missed something in terms of what's appropriate to ask here. I'm a new user and I'm still learning the ropes, so to speak.