At first, it seemed incredible that a bug like this could find its way into a shipping product, and it becomes even more annoying when you realize you probably won’t see a fix for it until you buy another phone. But there’s probably a simple explanation for it, and the fact is, everything works fine for a lot of people (but I’m going to stop just short of apologizing for Microsoft, because it’s annoying the hell out of me).
The problem is this: when you delete items from certain IMAP servers, they don’t stay deleted. My guess is that this is common on IMAP servers like the one I use, where everything is organized under one top-level folder (INBOX, in my case). When the Smartphone’s Pocket Inbox goes to create Deleted Items (or whatever folder it wants) in the root of my IMAP space, it fails and so does the delete.
So, there’s a simple workaround: use the move option (right menu, 5) to move it to your trash folder (in my case, INBOX.Trash), and then do a sync (right menu, 9). I have a feeling this problem would go away if I could tell Pocket Inbox to use INBOX as the top-level IMAP folder, though.