I migrated a VP of our company to Office 365 and now he's not seeing emails in folders that there should be. The problem seems to affect all folders but only emails after about 6-12 months old.
Other "clues" I've found are:
- Emails can be seen from the Office 365 Outlook Web Access interface
- The folders in Outlook will show the proper count of emails 
- Outlook is pointed to an exchange server (Office 365)
I suspect it's some sort of "don't sync if older than X" type setting but I have no idea where that setting would be.