I have not set my Gmail up under exchange, but I now have a "delete" option, "move" option, and "mark" option when I edit my Gmail. It was not there before (I had the "archive" option) and I don't know when it changed! I have an iPhone4 with iOS5. One day last week, I was "locked" out of Gmail for some reason (would not accept my password) and had to do some searching to find a link to "unlock" my account. Maybe something was going on then?
If you go into Gmail under "Accounts" instead of the "Inbox" you will see all of your folders for Gmail, including Trash.