Markwmsn, I believe the phone succeeds in moving the email to the trash, but then for whatever reason rereads a local, out of date copy of its inbox contents. Refreshing does not help. If the deletion was failing it should return an error message...there is a large history of such if you search for "iphone imap cannot move message to trash" or similar, where the user doesn't have the trash folder configured properly.
Goligo, our server also has UW-IMAP. If I get some time around our newborn (ha) I may be able to test on a Dovecot server. One thing I should mention is that in my case the mail server uses OpenWebmail, which actually uses POP to display and delete messages. However iOS mail has worked fine for me since I started using IMAP on this account almost four years and several iOS versions ago.
Steven Jones3, "It's as if the Mail client in iOS can't file away the message in the trash on the phone" ...if I understand iOS correctly it actually should not be able to do that; that's the reason for the error message in my first paragraph. IMAP should be configured to delete to a folder on the mail server. Since in my case the deletion appears to succeed that implies to me the mail app is not rereading the inbox contents correctly and ends up showing a phantom message.