Instead, Outlook will return a “There are no items to show in this view” message. The folder in the folder navigation pane displayed the proper number of (unread) items in the folder.
This could be the symptom of an issue which was already solved in Exchange 2010 Service Pack 1 Rollup 5. It seems the Office 365 data centers are not running a current version of Exchange, as today I received the message the Office 365 environment is currently being upgraded with Exchange 2010 Service Pack 2. The message also mentions the upgrade is to be completed at the end of the month.
More information on the issue in knowledge base articles kb2500648, announcing the fix is included in Exchange 2010 SP1 RU5.
Until then, the suggested workaround is to click one of the columns twice after which Outlook will update the view properly. Of course, you could also enable cached mode, if your setup and company policy permits (e.g. not running Outlook on terminal server).