“Mailbox does not exist” errors for Microsoft 365 mailbox backups

In August 2023, Microsoft made unannounced changes to hosted Exchange Mailbox service in Microsoft 365 (formerly Office 365).

These changes affect the “Contacts” folder in everyone’s mailboxes. It results in mailbox backups now aborting prematurely with the error, “Mailbox does not exist”.

This misleading and factually incorrect error message comes directly from Microsoft, causing BackupAssist 365 to abort the current user mailbox and move to the next one.

We are aware of this situation, and are currently working around this problem.

We wish to advise our users that:

1. We empathize with the frustration that this has caused.
2. This issue is caused by changes at Microsoft’s end. It looks plainly like a bug, introduced and rolled out in August 2023.
3. We know this because BackupAssist 365 has been backing up Contacts for over 5 years, and that part of our code has not changed in that time. Yes, it’s that stable.
4. We are now doing R&D into working around this Microsoft bugs.

Technical information about Microsoft’s magical disappearing mailboxes

BackupAssist’s mailbox backup code is conceptually straightforward. When processing the Contact list, we:

1. Find a list of folders in a mailbox using the FindFolder request.
2. Get a list of items in each folder using the FindItem request.

This has worked for over 5 years against Microsoft’s online Exchange offerings, and many more years against Exchange on-premise.

In August 2023, it stopped working. We investigated why, and found:

• FindFolder request (which also returns subfolders) is executed successfully.
• FindItem request for the same folder returns ErrorNonExistentMailbox.

In other words, we can see the folders in a user mailbox and we’re told they exist… but when we try to look inside the folder, we’re told that the entire Mailbox does not exist.

This is hard to believe, so here is the raw XML response for good measure:

<Trace Tag="EwsResponse" Tid="4" Time="2023-08-28 12:40:55Z" Version="0.0.0.0">
  <?xml version="1.0" encoding="utf-8"?>
  <s:Envelope xmlns:s="http://schemas.xmlsoap.org/soap/envelope/">
    <s:Header>
      <h:ServerVersionInfo MajorVersion="15" MinorVersion="20" MajorBuildNumber="6699" MinorBuildNumber="34" Version="V2018_01_08" xmlns:h="http://schemas.microsoft.com/exchange/services/2006/types" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" />
    </s:Header>
    <s:Body>
      <m:FindItemResponse xmlns:m="http://schemas.microsoft.com/exchange/services/2006/messages" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:t="http://schemas.microsoft.com/exchange/services/2006/types">
        <m:ResponseMessages>
          <m:FindItemResponseMessage ResponseClass="Error">
            <m:MessageText>Mailbox does not exist.</m:MessageText>
            <m:ResponseCode>ErrorNonExistentMailbox</m:ResponseCode>
            <m:DescriptiveLinkKey>0</m:DescriptiveLinkKey>
          </m:FindItemResponseMessage>
        </m:ResponseMessages>
      </m:FindItemResponse>
    </s:Body>
  </s:Envelope>
</Trace>

How is it possible that a mailbox suddenly does not exist, when only 1 API call prior, BackupAssist 365 was happily talking to and querying that mailbox?

The answer can only be Microsoft magic.

Why the mailbox backup gets aborted

Unfortunately, this error message also causes BackupAssist 365 to abort the mailbox. “Mailbox does not exist” is classed as a terminal error. So there’s no point in trying to back up a mailbox that does not exist – is there?

But sadly, there are times where common sense and logic don’t work – and this appears to be one of them.

What does our hotfix do?

It seems clear that we cannot trust the error messages that get returned in this case.

Our hotfix skips over folders that show this error, and proceed with the next folder anyway.

This will at least allow the backups to continue, until Microsoft fix the actual problem. Your backup reports will now show an informational message, reporting which Contacts folders could not be backed up. This message will simply go away when Microsoft fixes the problem.

This hotfix was first made available on 30 August 2023. If we receive positive user feedback, we will roll this into the mainstream release within 2-3 days.

To all our users of BackupAssist 365 who rely on our software for backing up Microsoft 365: thank all our users for their patience and understanding… we at BackupAssist are trying to make the best of a thoroughly unsatisfactory situation.