EWS API - Error when recreating notification subscriptions

When working with pull subscriptions to Office365 calendar folders, I've been getting a lot of ErrorReadEventsFailed messages in the SendNotification request. This error essentially means that the subscription can no longer be found, and the server should no longer expect new notifications.

Checking Microsoft's recommended error handling, the solution is to use Autodiscover to rediscover the ExternalEwsUrl or EwsPartnerUrl, and create a new subscription.

With Office365, the AutoDiscovery service seems near impossible with a combination of OAuth2 service accounts so I've been using https://outlook.office365.com/EWS/Exchange.asmx as the main EWS endpoint.

However, when I try to create a new subscription for the specific calendar folder, I keep getting a generic 500 ErrorNoRespondingCASInDestinationSite error:

Exchange Web Services are not currently available for this request because none of the Client Access Servers in the destination site could process the request.

The strange part is this only happens directly after receiving the initial ErrorReadEventsFailed error. If I try again in, say, 30 seconds, the request goes through without a problem.

After doing some research, it seemed that most users found it helpful to ensure that the X-AnchorMailbox header was set properly for the user that the service account wishes to impersonate. I double-checked this header, and it is indeed being sent along the request to resubscribe.

This problem may be solvable by an exponential back-off solution, or by just retrying X amount of times until the request goes through. It seems to me that when the subscription gets "lost", the O365 service needs time to change the DNS of the Exchange server (it's the only thing I can think of).

Any help would be greatly appreciated!

Given the documentation at: https://msdn.microsoft.com/en-us/library/office/dn458788(v=exchg.150).aspx

When a subscription is lost, or is no longer accessible, it is best to create a new subscription and not include the old watermark in the new subscription. Resubscribing with the old watermark causes a linear scan for events, which is costly.

Instead, create a new subscription and compare folder properties to look for content changes that occurred between the lost subscription and the new subscription. The extended folder properties that we recommend that you check are PR_LOCAL_COMMIT_TIME_MAX (0x670a0040) and PR_DELETED_COUNT_TOTAL (0x670b0003).

You can do this by creating an extended property definition. I think this may help you!!