You could use lazy_expunge with a namespace. Although it's marked as deprecated, so that might go away at some point. There have been some thoughts about the ability to remember the original folder also in the mailbox-based lazy_expunge folder, but it's not in any near future plans.