InefficientFilter error on Microsoft Graph requests which were previously working

Making the following request to the MS Graph to retrieve flagged messages ordered by due date:

https://graph.microsoft.com/beta/me/messages?$filter=flag/flagStatus%20eq%20%27flagged%27&$orderby=flag/dueDateTime/dateTime%20desc&$top=100

would previously succeed and give back the expected results. Recently some users have been getting the following response:

{
  "error": {
    "code": "InefficientFilter",
    "message": "The restriction or sort order is too complex for this operation.",
    "innerError": {
      "request-id": "5ef714c9-39a0-4167-a4d0-3682dcb46de4",
      "date": "2016-11-17T16:41:16"
    }
  }
}

Has a bug been introduced into the graph?

It is strange that this request was previously fine, and is now seen as inefficient. It also only happens on some users' accounts.

The same issue has also occurred with the following request to retrieve email attachments ordered by received date:

https://graph.microsoft.com/v1.0/me/messages?$filter=hasAttachments%20eq%20true&$orderby=receivedDateTime%20desc&$expand=attachments($select=name,contentType,size,lastModifiedDateTime)&$top=6

which now gets the same InefficientFilter error response. Note, the second request is to the v1.0 API so this is not limited to beta.

Also note that removing the orderby clause on the affected accounts will cause the requests to succeed.

This was an intentional (and breaking) change made to address a major issue with filtering. $orderby is still very much a thing.

To sum up from that link, if you use both $orderby and $filter in a request:

1. Any fields in $orderby MUST also be in $filter.
2. Order of fields in $filter matters:
   1. Fields that are also in $orderby MUST come first in the $filter and MUST be in the same order.
   2. Fields that are not in $orderby MUST come after the fields that are in $orderby.

So according to those guidelines, the problem with your request is that flag/dueDateTime/dateTime is not present in $filter.