I'm not sure but it could be a change they made in April: https://shopify.dev/changelog/host-parameter-added-to-the-oauth-redirect-uri
We had not updated our OAuth code in quite a while, and after investigating found that our flow was not following the current documentation at https://shopify.dev/apps/auth
After updating our code to follow the docs, it is working again.
The lesson here is that you really have to keep your eye on the change logs. Especially for OAuth because the API is not versioned. https://shopify.dev/api/usage/versioning#versioned-vs-unversioned-apis
This is an accepted solution.
I've found the reason why! They've changed the authorization URL from '.../admin/oauth/request_grant' to '.../admin/oauth/authorize' and that's it! That's it!
After the change, everything starts working again!