How do you delete a message?
The only real way to delete a message in Gmail is by moving to the Deleted folder -- which should be mapped to [Gmail]/Deleted (or [Gmail]/Bin depending on your account's language in Gmail / web).
To check the mapping:
Long press the account -> options and folders -> folders.
Find [Gmail]/Deleted (in Aqua 1.5.5) or "[Gmail]" and then "Deleted" under it (in Aqua 1.5.7).
Tap this folder and choose "Sync with [ Deleted ]".
Oh, I guess you're using push, correct?
