Exchange hybrid - 404 REST API is not yet supported for this mailbox

I'm trying to access an on-premise Exchange mailbox using the Microsoft Graph REST API as described here: https://docs.microsoft.com/en-us/graph/hybrid-rest-support

I have Exchange 2016 configured in hybrid mode and synced to Office 365.

This setup worked for several days - I could read on-premise mailboxes by sending REST requests https://graph.microsoft.com. It suddenly stopped working on Dec. 1.

Currently, I can perform the Oauth2 flow, but when sending an API request to https://graph.microsoft.com/v1.0/me/messages I get this 404 error:

{
    "error": {
        "code": "MailboxNotEnabledForRESTAPI",
        "message": "REST API is not yet supported for this mailbox."
    }
}

When using Graph Explorer (https://developer.microsoft.com/en-us/graph/graph-explorer) on the same mailbox, the API works as expected, i.e. no error and I can read the mailbox contents. So it doesn't seem like any problem in the hybrid configuration itself. On top of that, using the access token generated by Graph Explorer in Postman works as well.

I've compared the tokens using https://jwt.ms and couldn't find any differences except for one-time internal values. I used the following scope in the Oauth request: openid profile User.Read email Mail.Read

Any ideas? I'm aware that on-premise REST API is in preview, but has Microsoft dropped this feature? It worked fine until the beginning of the month. It seems that perhaps Graph Explorer, as a Microsoft app, has some special authorization, but I doubt that's the case.

Edit: I compared the tokens generated by the oauth request in jwt.ms, between the graph explorer and my Azure Apps (I tried several). Aside from timestamps, the different values are the app id, values which according to the documentation are one-time values. The values are: nonce, aio, uti, rh, sub (under xms_st)