Google geocoding API: OVER_QUERY_LIMIT despite very low usage

When using the geocoding API (server-side), the error Geocoding Service: You have exceeded your rate-limit for this API is returned in 100% of the cases since the start of this month/year. The data is entered manually by a very small group of users, so the rate of requests per second can not actually be exceeded. Nevertheless, all requests fail, according to the Google dashboard with status 403: "OVER_QUERY_LIMIT".

I have a valid API key, billing enabled and a valid credit card (the Google Maps Javascript API works without an issue using the same billing account)
The API key is restricted by the web server's IP address
I'm addressing the URL https://maps.googleapis.com/maps/api/geocode/json?address=ADDRESS&key=KEY, so it's not an SSL issue and the key is included
The dashboard shows we're way below quota (< 20 of 500 calls per day, at most 0.0018 requests/second, < 50 calls this month)
The issue persists even after the daily reset at 12:00 AM Pacific time

I've seen people suggest the Geocoding API is just buggy and other services would be preferable, or recommend a switch from server-side to client-side. The API call is made from a third party PHP module, so switching to another service or client-side geocoding would mean rebuilding the functionality from scratch. I'd like to avoid that, especially as we're nowhere near the actual quota. Does anyone have an idea what's going wrong?

Solution

The quotas "requests per 100 seconds" and "requests per user per 100 seconds" were too low. Despite them never being reached, the API did not function correctly with the limits set to 50/20. I set both limits to 100, now it works.