The problem was in the max_age query parameter of the authorization URL provided by our client (the one that a client redirects a user to in order to get an authorization code). The max_age had a value of 0 (e.g. max_age=0) which for some reason caused Entra to issue an authorization code that would provide a token that was seemingly issued 5 minutes in the past and immediately expired in the present. We fixed it by removing the query parameter altogether. This resulted into getting a token with the default 60-90 minutes lifetime. More about the query parameter can be read in the OIDC specification.