And please also do this:
Long press the account -> options and folders -> folders
Let the folder list refresh
Find the server side Deleted folder (may be called Trash, Deleted Items, Deleted Messages, or something else)
Tap this folder's name, choose "Sync with Deleted"
Now back out to the app's main window and try deleting again.
And one more thing: the app's "delete message" icon should be a "trash can", can you please confirm this for me?