Your issue sounds familiar. Let me explain the issue I had a while ago maybe it helps you.
I used the custom authorizer and in API Gateway and disabled the Cache. In spite of that it cached the authorize request!
I was sending GET and POST to the same resource. First time that I send a GET the request, it worked fine. Any GET request would work fine but I couldn’t send a POST request for that resource. If I would wait for few minutes and send a POST, it would work again but this time GET had problem.
I solved this issue by changing the returned policy. Each time I send back the policy I allow both GET and POST for that resource. If this change doesn’t make any vulnerability on your system you can try it.
Thanks, @armanfatahi! When you say “send back the policy I allow both GET and POST for that resource”, is that done on the API Gateway or somewhere else?