Microsoft Graph error: HTTP 503 "Mailbox info is stale"

Symptom

Backups of certain Exchange mailboxes fail consistently after migration from the Exchange Web Services API to the Microsoft Graph API. The error 503 MailboxInfoStale is returned on every Graph mail call. Backups of specific mailboxes fail on every run, while other mailboxes in the same tenant backup normally. The issue usually, but not necessarily, starts just after migration. The affected mailboxes can be opened in Outlook on the web, and can send and receive mail.

Cause

The condition is a stale per-mailbox routing state inside Exchange Online. It is per mailbox, not per tenant, per domain, per mailbox type, or per guest status. Other mailboxes of the same type, in the same tenant, on the same domain, using the same application, and using the same permissions succeed at the same moment.

• No discriminator appears between the affected mailboxes and healthy ones. Account type, product, generation, guest status, routed domain, creation date, tenant and directory are all identical across both groups. 
• We cannot say which backend serves an affected mailbox. The error body carries no database or server value, and the response headers we now capture place the affected mailboxes across five Microsoft regions rather than on one shared backend. We cannot support the claim that these mailboxes share a bad database, and the request IDs are stronger evidence than any inference about their infrastructure.
• This is not an X-AnchorMailbox problem. Anchoring the request on the mailbox GUID does not route around a stale mailbox record. The issue will not be resolved by further code changes to anchoring.

Solution

No configuration change, code fix or self-service action exists to clear this error. The only route forward is for the customer to raise a Microsoft support case from their own tenant, asking Microsoft to clear the stale backend routing state. 

To proceed, follow the steps below.

1. Run the following checks (estimated time: 5 minutes). This will rule out SMTP issues, which is the only cause of this error that the customer can fix themselves. Run the checks in the Exchange Online Management PowerShell module. 

Connect-ExchangeOnline

$u = "user@domain.tld"

# 1. Malformed proxy addresses: the only customer-fixable cause of Exchange 503
Get-Mailbox -Identity $u | Select-Object -ExpandProperty EmailAddresses

# 2. Mailbox identity and the backend database it is homed on
Get-Mailbox -Identity $u | fl Name,UserPrincipalName,ExchangeGuid,RecipientTypeDetails,IsDirSynced,ExternalDirectoryObjectId,WhenCreated
Get-MailboxStatistics -Identity $u | fl DisplayName,Database,LastLogonTime,TotalItemSize

# 3. Stalled move request or soft-deleted duplicate
Get-MoveRequest -Identity $u -ErrorAction SilentlyContinue
Get-Mailbox -SoftDeletedMailbox -Identity $u -ErrorAction SilentlyContinue

The following checks are included:

If all checks come back clean, there is nothing further the customer can do on their side. Proceed to the support case.

2. Gather diagnostic data from CyberSentriq Support. Microsoft closes cases that do not have correlation data. The failing calls are made by CyberSentriq, not by the customer, so the customer cannot capture these headers. Since September 16, 2026 our Exchange service records them on every stale failure, so Support can supply them per mailbox on request.

Ask Support for a list of affected mailboxes with a recent request-id, client-request-id and timestamp for each, and attach the list to the Microsoft case. Do not attach the error body: it contains only the code and the sentence "Mailbox info is stale".

3. You can now log a support case with Microsoft. To do this: 

• Sign in to the Microsoft 365 admin center. 
• Go to Support > New service request. 
• Set the service to Exchange Online and the severity to B at minimum. This is a production impact with no workaround. 
• Use this subject line: "503 MailboxInfoStale on Microsoft Graph for specific mailboxes"

Paste the message body below, ensuring that you fill every placeholder.

Hello,
A specific set of mailboxes in our tenant cannot be reached through the
Microsoft Graph mail API. Every call returns:
  HTTP 503 - "code": "MailboxInfoStale"
Tenant ID: [tenant GUID]
Affected mailboxes: [count] (list attached, with Microsoft request ids)
Examples: [upn1], [upn2], [upn3]
Failing since: [date] [time] UTC, 100% of calls, every attempt
These mailboxes are healthy: users can open them in Outlook on the web and
send and receive mail normally. They were also backed up successfully over
Exchange Web Services on [date] at [time] UTC, roughly two hours before the
first Graph failure at [time] UTC the same day.
All other mailboxes in the same tenant, same domain and same mailbox type
work with the same application and the same permissions, at the same moment.
The affected mailboxes have been addressed by SMTP address, by Entra object
id, and anchored on the mailbox GUID. All three return the same 503. We have
confirmed valid proxy addresses and no pending move requests.
The attached file lists, per mailbox, the Microsoft request-id and
client-request-id of a failing call and its UTC timestamp.
We believe this is stale per-mailbox routing state on the Exchange Online
backend. We are asking you to:
1. Trace the attached request ids and tell us why routing is stale for these
   specific mailboxes.
2. Clear the stale routing state, or rehome the mailboxes onto a healthy
   database.
Business impact: these mailboxes have had no successful backup since [date].
Exchange Web Services retires on 1 October 2026 and is currently the only
protocol that demonstrably reaches them, so after that date they cannot be
protected at all.
Thank you,
[name]

4. Attach three things: 

• the affected mailboxes with the Microsoft request IDs supplied by CyberSentriq Support
• a comparable set of mailboxes in the same tenant that work normally
• the output of the checks above.

The comparison is what makes the case concrete; the request IDs are what make it traceable.

If the first-line agent responds with a permissions explanation or suggests using X-AnchorMailbox, ask for escalation to the Exchange Online backend team. Graph front-line support does not touch database routing. 

See the table below for further responses not to accept as a resolution.

The sources below may also be useful to the customer as a reference.