Perhaps it is a problem with the Courier server my ISP uses for IMAP4.
Here is my test and the results.
1) Send email to myself, I see it on the device and on the desktop.
2) Close desktop client to be sure it would not interfere.
3) Delete email on my Q, I see it goes into my Deleted items folder.
4) Send/Receive emails and I see the items disappear from my inbox and deleted items.
5) Send/Receive a second time and they reappear in my inbox.
6) Open desktop client and see the message has reappeared.

* I am running no other desktop program that might re-add this item to the inbox.

I shall go try with my fastmail account as well. Perhaps it only works with Exchange... Microsoft, go figure...