Cumulative Update 6 (CU6) for Exchange Server 2016 will be released soonTM, but before that happens, I wanted to make you aware of a behavior change in item recovery that is shipping in CU6. Hopefully this information will aid you in your planning, testing, and deployment of CU6.
Prior to Exchange 2010, we had the Dumpster 1.0, which was essentially a view stored per folder. Items in the dumpster stayed in the folder where they were soft-deleted (shift-delete or delete from Deleted Items) and were stamped with the ptagDeletedOnFlag flag. These items were special-cased in the store to be excluded from normal Outlook views and quotas. This design also meant that when a user wanted to recover the item, it was restored to its original folder.