While setting up Provisior at a new customer we ran into an error while testing the on-boarding of a new user. The mailbox could not be enabled in the local Exchange 2013 server.

The error Exchange returned was: Load balancing failed to find a valid mailbox database.

Fortunately Google helped us pretty fast. Following the tips in this article, we used these Powershell commando to check if the Exchange database was excluded from provisioning:

Get-mailboxdatabase | ft name,isexcludedfromprovisioning
Get-mailboxdatabase | ft name,issuspendedfromprovisioning

If any of the statements returns true, than that is the issue. Run the following commands to enable them:

Set-MailboxDatabase "MailboxDatabaseName" -IsSuspendedFromProvisioning $false
Set-MailboxDatabase "MailboxDatabaseName" -IsExcludedFromProvisioning $false

As mentioned in the article, if disk space has been running low on the Exchange server these settings can be changed to true. So this is really a situation the can occur in existing Provisior instances as well.