My issue was that I wasn't very familiar with ipv6, and my ISP (OVH) apparently gave my server a range of about 256 ipv6 addresses, and I didn't really know how to properly set up reverse DNS and SPF. After spending a day or two getting nowhere, I just decided to turn off ipv6 completely for the server.
This was my experience, too. I took this advice [1] configuring postfix and Gmail started to accept my emails.
[1] https://christian.skala.me/blog/gmail-why-are-you-doing-this...