"The mailbox could not be associated to a store in the database" (4236604)

The Exchange mailboxes task when run against Exchange 2010 servers has the following warning for numerous mailboxes: "The mailbox could not be associated to a store in the database.

When viewing the list of tasks that ran for the Default Gathering you can see that both the Exchange Information Stores and Exchange Databases tasks ran against the Exchange 2010 servers

In addition, the reports may have only partial data for the mailboxes reported in the warning.

Gathering corruption. The Exchange Information Stores task is not supposed to run against Exchange 2010 servers, only the Exchange Databases task.

Delete the Default Gathering and recreate it.

1. In the Left-Pane of the MessageStats Console, Expand Tasks
2. Note the time your current Default Gathering is scheduled to run
3. Right-click your Default Gathering and select Delete
4. Right-click your Exchange Organization and select Create Task
5. Select the Default Gathering Template
6. Click Next until you get to the Task Schedule page
7. Uncheck Use Default Configuration
8. Select Daily for the Task Period
9. Enter the Start Time noted in step 2
10. Click Next all the way through the rest of the task wizard.
11. Allow your Default Gathering to run and confirm a successful gathering