Sending mails with PHP and being blocked by Google

Sending mails with PHP is one-liner:

<?php

mail('bob@example.com', 'Hey Bob!', 'This is your mail!');

But Google was blocking every mail that I've tried to send to a @gmail.com address, with this error message:

Our system has detected that this message does not meet IPv6 sending guidelines regarding PTR records and authentication. Please review https://support.google.com/mail/?p=IPv6AuthError for more information.

The link leads to an article about SPF, DKIM, DMARC and other spam protection techniques available. My DNS settings at that time already featured SPF and DMARC records, as well as reverse DNS entries for the IPv4 and IPv6 addresses of my server. I even added the domain on postmaster.google.com, but to no avail.

There was one thing missing: the AAAA record, which maps the domain name to the IPv6 address of my server. I don't know why it wasn't there in the first place, but after adding it the mails went finally through.