Transaction State ‘Not Processed’

We are seeing some intermittent failures (Transaction State ‘Not Processed’) that are happening once in a while using the Payments API. The following is the error message "The required Authorization header was missing or invalid, or the token has expired".  They don't happen all the time but we do see these failures. Our API call to 'Checkout' the transaction is immediately after the card authorization and is the same for every call. We see a bunch of transactions that are processed successfully without any issues (before and after these failures) with in minutes. Which makes me think that the token for these transactions are expiring. Seems like the chances of it happening is more if there is a bigger load of transactions with in a short time frame (just an observation). We also made changes to the code to retry one additional time by generating a new access token and resubmit the API call but still not able to Checkout the transaction. Any one else having this issue?

Thanks

Ravi