NonExistentMailboxException can simply mean that the mailbox in an inconsistent state
Here’s an issue that’s actually very easy to investigate and fix, but might get you puzzled if you are not looking in the right place. The symptoms were that several users were suddenly unable to get free/busy information, configure OOO, get MailTips, etc. Autodiscover was failing with 401 error; trying to …