Why would I get a Forbidden message from AWS API Gateway, even though things are working internally?
You might be running into some VPC-related limits. See https://winterwindsoftware.com/scaling-lambdas-inside-vpc/. Sounds like you might be running out of ENIs. You could try moving the function to a different VPC. How long does each invocation of the lambda run for? And what language is you lambda written in?