Hi Martin,
This can sometimes happen on Office 365's side, I have spent time on support calls where a users shared mailbox will suddenly stop searching properly, attempting to re-index etc. does nothing.

Very frustrating! The problem self resolved by the next morning.

Hope this is something similar and also self resolves for you :P