The only way deleting a message works in a Gmail account is if you move it to the Deleted folder, which in turn has to sync with [Gmail]/Trash (or whatever it's called, mine is in Russian, [Gmail]/Корзина).
Both of these are the defaults in my app.
This is how Gmail's IMAP server works, it's by design on their part.
Doing a "delete now" in a Gmail / IMAP account will only remove the label that corresponds to the folder (where you're deleting from). It will not truly delete the message.
Oh, and this is IMAP of course... which again is the default for @gmail.com accounts... Since yours is a Google Apps account, please long press the account, choose Account setup, then Manual, and verify that you're using IMAP, connecting to imap.gmail.com, SSL, port 993.