I think I found the issue, pointing me to the internal storage was a very good hint. So what I did to test this was to issue myself a very long running JWT. I used the exact same token for the unversioned API as well as for the next test with the same API which was then versioned (which then results in: “Access to this API has been disallowed”). When I looked up the key from the internal storage I saw that it had the Default version of the API as granted access although the permissions of the policy have been changed such that they grant access to v1 and v2 and Default does not exist anymore.
When I issued myself a new JWT, i.e. different principal (sub field), and sent a request again the access worked. My guess is that the access rights are not evaluated again if the same principal is seen multiple times?