Not receiving mail or even connection attempts from Google

I recently installed and configured my own postfix mail server on a vps. It uses a LetsEncrypt wildcard certificate, has a PTR DNS record with the vps' IP-address pointing to my mail server's hostname and is configured with SPF and DKIM (but no DMARC yet) and ufw is configured to allow incoming connections on ports 25,80,443,587,993.

Everything appeared to be working just fine: the mail server receives incoming mail from just about anybody except for mails from Google, as I discovered today:

I made multiple attempts today to create a Google account with one of my own mail addresses, but each time I failed to receive verification codes, even though Google told me they send one. In fact: /var/log/mail.log does not even list any connection attempts from Google.

I then tested creating a Google account with a temporary email address from a well known webmail provider and there the verification code came through without a problem.

So, this all leads me to believe there's some misconfiguration of my mail server.

My assumption is that Google has very strict security measures in place to verify the authenticity of mail addresses and/or mail servers, but I'm not knowledgeable enough to know where to look exactly.

Here's my /etc/postfix/main.cf (domain redacted as <mydomain>):

smtpd_banner = $myhostname ESMTP $mail_name
biff = no

# appending .domain is the MUA's job.
append_dot_mydomain = no

# Uncomment the next line to generate "delayed mail" warnings
#delay_warning_time = 4h

readme_directory = no

# See http://www.postfix.org/COMPATIBILITY_README.html -- default to 2 on
# fresh installs.
compatibility_level = 2

# TLS parameters
smtpd_tls_cert_file=/etc/letsencrypt/live/<mydomain>/fullchain.pem
smtpd_tls_key_file=/etc/letsencrypt/live/<mydomain>/privkey.pem
smtpd_tls_security_level=may
smtpd_relay_restrictions = permit_mynetworks permit_sasl_authenticated defer_unauth_destination

smtp_tls_CApath=/etc/ssl/certs
smtp_tls_security_level=may
smtp_tls_loglevel = 1
smtp_tls_session_cache_database = btree:${data_directory}/smtp_scache
smtpd_recipient_restrictions=reject_unknown_client_hostname,check_policy_service unix:private/policyd-spf

# Host parameters
myhostname = mail.<mydomain>
alias_maps = hash:/etc/aliases
alias_database = hash:/etc/aliases
myorigin = /etc/mailname
masquerade_domains = $mydomain
mydestination = $myhostname, <mydomain>, vps.<mydomain>, localhost.<mydomain>, localhost
relayhost = 
mynetworks = 127.0.0.0/8 [::ffff:127.0.0.0]/104 [::1]/128
mailbox_size_limit = 0
recipient_delimiter = +
inet_interfaces = all
inet_protocols = all

# Connect to Postgres for mailboxes, transports and aliases
local_recipient_maps =
virtual_uid_maps = static:997
virtual_gid_maps = static:998
virtual_mailbox_base = /var/mail/vmail/
virtual_mailbox_maps = pgsql:/etc/postfix/pgsql/mailboxes.cf
virtual_alias_maps = pgsql:/etc/postfix/pgsql/aliases.cf
transport_maps = pgsql:/etc/postfix/pgsql/transports.cf

# DKIM
milter_default_action = accept
milter_protocol = 2
smtpd_milters = inet:127.0.0.1:8892
non_smtpd_milters = $smtpd_milters

...and here is my /etc/postfix/master.cf:

smtp      inet  n       -       y       -       -       smtpd
  -o disable_vrfy_command=yes
#smtp      inet  n       -       y       -       1       postscreen
#smtpd     pass  -       -       y       -       -       smtpd
#dnsblog   unix  -       -       y       -       0       dnsblog
#tlsproxy  unix  -       -       y       -       0       tlsproxy
submission inet n       -       y       -       -       smtpd
  -o syslog_name=postfix/submission
  -o smtpd_tls_security_level=encrypt
  -o smtpd_tls_auth_only=yes
  -o smtpd_sasl_auth_enable=yes
  -o smtpd_sasl_type=dovecot
  -o smtpd_sasl_path=private/auth
  -o smtpd_reject_unlisted_recipient=no
  -o smtpd_relay_restrictions=permit_sasl_authenticated,reject
  -o smtpd_recipient_restrictions=
  -o milter_macro_daemon_name=ORIGINATING
  -o disable_vrfy_command=yes
#  -o smtpd_client_restrictions=$mua_client_restrictions
#  -o smtpd_helo_restrictions=$mua_helo_restrictions
#  -o smtpd_sender_restrictions=$mua_sender_restrictions
#smtps     inet  n       -       y       -       -       smtpd
#  -o syslog_name=postfix/smtps
#  -o smtpd_tls_wrappermode=yes
#  -o smtpd_sasl_auth_enable=yes
#  -o smtpd_reject_unlisted_recipient=no
#  -o smtpd_client_restrictions=$mua_client_restrictions
#  -o smtpd_helo_restrictions=$mua_helo_restrictions
#  -o smtpd_sender_restrictions=$mua_sender_restrictions
#  -o smtpd_recipient_restrictions=
#  -o smtpd_relay_restrictions=permit_sasl_authenticated,reject
#  -o milter_macro_daemon_name=ORIGINATING
#628       inet  n       -       y       -       -       qmqpd
pickup    unix  n       -       y       60      1       pickup
cleanup   unix  n       -       y       -       0       cleanup
  -o header_checks=regexp:/etc/postfix/header_checks
qmgr      unix  n       -       n       300     1       qmgr
#qmgr     unix  n       -       n       300     1       oqmgr
tlsmgr    unix  -       -       y       1000?   1       tlsmgr
rewrite   unix  -       -       y       -       -       trivial-rewrite
bounce    unix  -       -       y       -       0       bounce
defer     unix  -       -       y       -       0       bounce
trace     unix  -       -       y       -       0       bounce
verify    unix  -       -       y       -       1       verify
flush     unix  n       -       y       1000?   0       flush
proxymap  unix  -       -       n       -       -       proxymap
proxywrite unix -       -       n       -       1       proxymap
smtp      unix  -       -       y       -       -       smtp
relay     unix  -       -       y       -       -       smtp
        -o syslog_name=postfix/$service_name
#       -o smtp_helo_timeout=5 -o smtp_connect_timeout=5
showq     unix  n       -       y       -       -       showq
error     unix  -       -       y       -       -       error
retry     unix  -       -       y       -       -       error
discard   unix  -       -       y       -       -       discard
local     unix  -       n       n       -       -       local
virtual   unix  -       n       n       -       -       virtual
lmtp      unix  -       -       y       -       -       lmtp
anvil     unix  -       -       y       -       1       anvil
scache    unix  -       -       y       -       1       scache
postlog   unix-dgram n  -       n       -       1       postlogd
#
# ====================================================================
# Interfaces to non-Postfix software. Be sure to examine the manual
# pages of the non-Postfix software to find out what options it wants.
#
# Many of the following services use the Postfix pipe(8) delivery
# agent.  See the pipe(8) man page for information about ${recipient}
# and other message envelope options.
# ====================================================================
#
# maildrop. See the Postfix MAILDROP_README file for details.
# Also specify in main.cf: maildrop_destination_recipient_limit=1
#
maildrop  unix  -       n       n       -       -       pipe
  flags=DRhu user=vmail argv=/usr/bin/maildrop -d ${recipient}
#
# ====================================================================
#
# Recent Cyrus versions can use the existing "lmtp" master.cf entry.
#
# Specify in cyrus.conf:
#   lmtp    cmd="lmtpd -a" listen="localhost:lmtp" proto=tcp4
#
# Specify in main.cf one or more of the following:
#  mailbox_transport = lmtp:inet:localhost
#  virtual_transport = lmtp:inet:localhost
#
# ====================================================================
#
# Cyrus 2.1.5 (Amos Gouaux)
# Also specify in main.cf: cyrus_destination_recipient_limit=1
#
#cyrus     unix  -       n       n       -       -       pipe
#  user=cyrus argv=/cyrus/bin/deliver -e -r ${sender} -m ${extension} ${user}
#
# ====================================================================
# Old example of delivery via Cyrus.
#
#old-cyrus unix  -       n       n       -       -       pipe
#  flags=R user=cyrus argv=/cyrus/bin/deliver -e -m ${extension} ${user}
#
# ====================================================================
#
# See the Postfix UUCP_README file for configuration details.
#
uucp      unix  -       n       n       -       -       pipe
  flags=Fqhu user=uucp argv=uux -r -n -z -a$sender - $nexthop!rmail ($recipient)
#
# Other external delivery methods.
#
ifmail    unix  -       n       n       -       -       pipe
  flags=F user=ftn argv=/usr/lib/ifmail/ifmail -r $nexthop ($recipient)
bsmtp     unix  -       n       n       -       -       pipe
  flags=Fq. user=bsmtp argv=/usr/lib/bsmtp/bsmtp -t$nexthop -f$sender $recipient
scalemail-backend unix  -   n   n   -   2   pipe
  flags=R user=scalemail argv=/usr/lib/scalemail/bin/scalemail-store ${nexthop} ${user} ${extension}
mailman   unix  -       n       n       -       -       pipe
  flags=FR user=list argv=/usr/lib/mailman/bin/postfix-to-mailman.py
  ${nexthop} ${user}

policyd-spf  unix  -       n       n       -       0       spawn user=policyd-spf argv=/usr/bin/policyd-spf

Do you have any idea why Google fails to send mail to my mail server? Could it be the lack of DMARC? Or could Google be attempting to send mail though another port than 25, perhaps? Is that a thing? Incoming mail through another port than 25?

Some additional information, in response to glts's answer, which may be relevant:

I do have an MX record pointing to my mail server:

However, the hostname (/etc/hostname) of my vps box is vps.<mydomain>. Only postfix is configured to listen to mail.<mydomain> (as you can see in main.cf). Could this perhaps be an issue?