API Gateway Randomly Switching Responses From 403 To 404

I have API Gateway set up to serve some files from S3 bucket with Lambda. When I try to request non-existing files, API Gateway sometimes responds with 403 Forbidden (most of the times and doesn't even trigger Lambda function) and sometimes with 404 Not Found error (I'd like to trigger 404 in such cases).

My Lambda function is very simple:

exports.handler = async event => {
  try {
    const Bucket = 'testing-bucket';
    const Key = `${event.documentType}/${event.requestParams.document}`;
    const file = await s3.getObject({ Bucket, Key }).promise();

    return {
      body: file.Body.toString('base64'),
      headers: {
        'Content-Disposition': `attachment; filename=test.jpg`,
        'Content-Length': file.ContentLength,
        'Content-Type': file.ContentType,
      },
      statusCode: 200,
      isBase64Encoded: true,
    };
  } catch (e) {
    return {
      body: JSON.stringify({ message: `[${e.code}] ${e.message}` }),
      statusCode: e.statusCode,
    };
  }
};

IAM Role attached to Lambda function is configured in this way:

{
    "Version": "2012-10-17",
    "Statement": [
        {
            "Sid": "VisualEditor0",
            "Effect": "Allow",
            "Action": [
                "s3:PutObject",
                "s3:GetObject",
                "s3:ListBucket"
            ],
            "Resource": [
                "arn:aws:s3:::testing-bucket",
                "arn:aws:s3:::testing-bucket/*"
            ]
        }
    ]
}

Caching is completely disabled in API Gateway and the command I've been trying to test this out is:

curl -X GET -H 'Authorization: 123xyz' -H 'Accept: image/jpeg' -H 'Cache-Control: no-cache' -I https://test.com/existing_folder/non-existing-file.xxx

Responses are:

HTTP/2 403
content-type: application/json
content-length: 60
date: Mon, 07 Oct 2019 10:32:30 GMT
x-amzn-requestid: ae870104-9045-4c23-9794-226992bad591
x-amzn-errortype: AccessDeniedException
x-amz-apigw-id: BMAZwGSyoAMFftw=
x-cache: Error from cloudfront
via: 1.1 ccf34ecc11e5579d8083b17d9d39a622.cloudfront.net (CloudFront)
x-amz-cf-pop: LHR62-C2
x-amz-cf-id: zgtgfJX9TQLcI8F2RLWdgTz-RN_1j7MXblQ1498ucoeFY3dhjitOdg==

and

HTTP/2 404
content-type: application/json
content-length: 59
date: Mon, 07 Oct 2019 10:32:31 GMT
x-amzn-requestid: 2de49681-4f21-4cd1-989c-9b36327badb1
x-amz-apigw-id: BMAZ5E52IAMFwEg=
x-amzn-trace-id: Root=1-5d9b143f-aadf0a24a5f60f4c939b77c0;Sampled=0
x-cache: Error from cloudfront
via: 1.1 be00537a2361673ea48963d6e04d04a1.cloudfront.net (CloudFront)
x-amz-cf-pop: LHR62-C2
x-amz-cf-id: 9VI26GH3-ZuJSQrEt5Fc7EjuMt8IV0TPzPwna8dvvr6UtsgiqwwIkw==

How to make API Gateway respond in consistent way?

UPDATE:

After observing API Gateway logs and trying to spam the same curl command for existing and non-existing files couple of times in a row, this was the output for non-existing file (timestamps are intact):

# curl -X GET -H 'Authorization: 123xyz' -H 'Accept: image/jpeg' -H 'cache-control: private, no-cache, no-store, max-age=1, s-maxage=1'  https://my.url/foo/nobar

{
    "requestId": "d19602e8-3a32-4445-b9e6-99f05a59fac4",
    "ip": "redacted",
    "caller": "-",
    "user": "-",
    "requestTime": "08/Oct/2019:00:05:03 +0000",
    "httpMethod": "GET",
    "resourcePath": "/foo/{bar}",
    "status": "404",
    "protocol": "HTTP/1.1",
    "responseLength": "59"
}

# and

{
    "requestId": "b33bf6c7-55db-4e1f-b4e4-b1e826139556",
    "ip": "redacted",
    "caller": "-",
    "user": "-",
    "requestTime": "08/Oct/2019:00:05:05 +0000",
    "httpMethod": "GET",
    "resourcePath": "/foo/{bar}",
    "status": "403",
    "protocol": "HTTP/1.1",
    "responseLength": "60"
}

and for existing file:

# curl -X GET -H 'Authorization: 123xyz' -H 'Accept: image/jpeg' -H 'cache-control: private, no-cache, no-store, max-age=1, s-maxage=1'  https://my.url/foo/bar

{
    "requestId": "122ef31e-c587-470c-a0b5-51c6d9838fe4",
    "ip": "redacted",
    "caller": "-",
    "user": "-",
    "requestTime": "07/Oct/2019:23:58:35 +0000",
    "httpMethod": "GET",
    "resourcePath": "/foo/{bar}",
    "status": "403",
    "protocol": "HTTP/1.1",
    "responseLength": "60"
}

# and then later

{
    "requestId": "c8ad1b40-006f-4d03-9d10-c6d91e366380",
    "ip": "redacted",
    "caller": "-",
    "user": "-",
    "requestTime": "07/Oct/2019:23:59:58 +0000",
    "httpMethod": "GET",
    "resourcePath": "/foo/{bar}",
    "status": "200",
    "protocol": "HTTP/1.1",
    "responseLength": "80280"
}

I finally got some time to get back to this issue and it looks like the problem was all along in "authorizer" function which had caching enabled, once disabled, my responses started to respond in a consistent way.