We came to the conclusion that our German IP (at Hetzner) is within a range that has previously been assigned to Iran, and was blocked due to stale geolocation data at Google.
As a workaround, we began contacting the API using an alternative IP.
In particular, in case it can help someone: We simply use IPv6 instead.