Microsoft recently announced that deleted item retention in Office 365 will now default to indefinite. Until now, items in Deleted Items were removed after 30 days. This was announced here:
In my newly migrated mailbox I had some old subfolders that had been removed and were in Deleted Items. There is no longer any content in those folders but all of the items directly in Deleted Items have been retained.