Third-party quota exceeded

Your product calls a third-party AI/maps API using a single shared API key with a per-key quota of 60,000 requests/minute. For months you're fine. A new feature shipped Monday that makes 4 calls per page view instead of 1, and on Wednesday a moderate traffic bump pushes you over the per-minute quota for the first time: you see a wall of 429 quota exceeded from the provider, user-facing features fail, and your own service CPU is fine. How do you triage and mitigate, and what's the durable fix?