Solution

For large Exchange Servers, in order to avoid having only one set containing hundreds or thousands of mailboxes and millions of items, it is recommended to configure several sets that can be managed easier and synchronized faster (if they become at some point unsynchronized).
In this example we create three EWS backup sets ( instead of one set), and still protect all mailboxes irrespective of the mailbox database they are located in.
( these sets will also backup automatically new mailboxes that will be created in the future):

1. Create the first EWS backup set (to backup the maiboxes starting with the letters a to g):
- expand the tree, highlight and add the second-level entry "VirtualShare:Exchange Mailboxes" to the backup items list;
- expand the tree again, highlight the second-level entry "VirtualShare:Exchange Mailboxes", click on the "RegEx" button;
- click on "Custom" option, in the box available for this field place the string below:
\\[a-g].*
- select "Inclusion" and deselect the 'Negate" and "Case Sensitive" options, ensure the "Match: files and directories" is set, click "ok" to apply the regex to the backup selection, then "Next" to see the subsequent pane of the New backup set wizard.


2. Create the second EWS backup set (to backup the maiboxes starting with the letters h to o):
- expand the tree, highlight and add the second-level entry "VirtualShare:Exchange Mailboxes" to the backup items list;
- expand the tree again, highlight the second-level entry "VirtualShare:Exchange Mailboxes", click on the "RegEx" button;
- click on "Custom" option, in the box available for this field place the string below:
\\[h-o].*
- select "Inclusion" and deselect the 'Negate" and "Case Sensitive" options, ensure the "Match: files and directories" is set, click "ok" to apply the regex to the backup selection, then "Next" to see the subsequent pane of the New backup set wizard.


3. Create the third EWS backup set (so that only the remaining mailboxes starting with [p-z] will be backed up)
- expand the tree, highlight and add the second-level entry "VirtualShare:Exchange Mailboxes" to the backup items list;
- expand the tree again, highlight the second-level entry "VirtualShare:Exchange Mailboxes", click on the "RegEx" button;
- click on "Custom" option, in the box available for this field place the string below:
\\[p-z].*
- select "Inclusion" and deselect the 'Negate" and "Case Sensitive" options, ensure the "Match: files and directories" is set, click "ok" to apply the regex to the backup selection, then "Next" to see the subsequent pane of the New backup set wizard.

The same logic can be applied if in need to create more than 3 backup sets.