We have a number of users who are now convinced that Outlook is not fit for purpose, as they have deleted a large number of emails, only for them to return to their original location shortly afterwards.
Interesting, if they have OWA open at the same time, they never seem to disappear from OWA. When deletion works, they disappear immediately. Suggests some kind of sync issue to me. We know that they are on struggling hardware - is it possible that this is issue?
Hardware may be the issue. Had a Windows phone (using Outlook) that did exactly the same, delete emails from "Deleted" folder, few hours later, back in the "Deleted". Changed the phone and haven't had the issue since.