New 500 Response on POST https://graph.microsoft.com/v1.0/subscriptions (The operation failed with a permanent mailbox error)

We have an Outlook add-in, using the java SDK version 2.6.0.

Since last Weds 23rd April (the error definitely first occurred then), the authentication process (creating a subscription) on the add-in is failing for some users, with a response of 500:

Unexpected response from Graph API: 500: com.microsoft.graph.http.GraphFatalServiceException: Unexpected exception returned from the service.
Error code: ExtensionError
Error message: Operation: Create; Exception: 
	[Status Code: InternalServerError; 
	Reason: The operation failed with a permanent mailbox error.
	Error Details: CallFailedException:Cannot query rows in a table.,
	MapiExceptionCallFailed:MapiExceptionCallFailed: QueryRows operation has failed 						(hr=0x80004005, ec=-2147467259)#0121.84300:A4000000, 1.84300:12000000, ...]

POST https://graph.microsoft.com/v1.0/subscriptions
	Prefer : IdType=ImmutableId
	SdkVersion : graph-java/v2.6.0
	SdkVersion : graph-java/v2.6.0
	Authorization : [PII_REDACTED]#012{"changeType":"created","clientState":"4e705bd1cbb[...]

Some of the code creating the subscription:

val client = graphClient(service)
val config = notificationConfig(service)

val subscription = new Subscription()
subscription.changeType = events.map(_.entryName).mkString(",")
subscription.notificationUrl = config.notificationUrl
subscription.resource = "me/messages"
subscription.expirationDateTime = ...
subscription.clientState = ...

val result: Subscription = client
	.subscriptions()
    .buildRequest(options.asJava)
    .post(subscription)

GraphSubscription(result)

Are there any known changes that could be causing this? We haven't made any changes that we'd expect to impact this.