[SalesForce] (400) Bad Request when attempting to use refresh tokens

Our application interacts with our clients' Salesforce instances using the REST API and refresh tokens we have stored on our database. Every API request will use that refresh token to get an access token to perform transactions.

There are a small subset of clients that are receiving errors when attempting to use the application. According to our logs, when attempting to use those clients' refresh tokens, Salesforce returns a (400) Bad Request error. Generating a new refresh token for the client seems to resolve the issue.

The flow of the app is as follows:

1. User enters app
2. App checks if a refresh token for the client is stored in the database
3. If one is not available, get a new refresh token and store it in the database
4. Outside of Salesforce, the stored refresh token is used to generate an access token every time an update is needing to be made in Salesforce using the Rest API
5. That access token is used only for the one call, never used again.

Based on this flow, the user should always be using the app's most recently granted token, so I don't see how that token would get invalidated.

I'm curious as to what would cause certain refresh tokens to become invalid? They aren't supposed to expire, so what might be the cause?