Microsoft has acknowledged that some users will be experiencing limited success searching for email items from within Outlook. The problem is server based and is not caused by your mail client.

As a work around, users can either select All Mail Items when performing a search within Outlook or they may use the Office 365 web interface to search for mail items on a targeted folder.

This notice will be updated when Microsoft confirms the problem as resolved.