The first domain, the one that the PTR for the IP is pointing at is well over 2 years old, the second domain is not even a week old, however, I recently switched to a new VPS, with a new IP address, that was around a week ago. I guess the DNS has propagated now, since its been a couple of days since the last change.
I ran both domains through the whole suite of tests at
mxtoolbox.com again, and it indicates that everything is set up correctly, including DKIM, SPF and the PTR record, as well as TLS.
As far as I can tell everything is configured correctly, which leads me to believe that the problem might be with the IP address. Perhaps it's been used to send spam in the past.
In the mean time I also ran some more tests, just sending some non-suspicious content to various email addresses of people I know. GMail is not the only service flagging them as spam. At least Outlook.com is also doing it, but some other services don't. Especially private mailservers with spamassassin are not flagging them as spam.