Problem:
You set someone up in Office 365 (this happened with a pre-existing account) and changed the domain away from onmicrosoft.com You get the following error:
exchange.data.storage.databasenotfoundexception
Solution:
Change the user’s default login name to user@domain.onmicrosoft.com, wait a few and change it back.
Wait a few.