I never delete. Tried now though, deleting works fine on my SGS and deletion occurs/snycs on desktop Gmail. Doesn't go into archive, goes into trash folder.
In order to DELETE the email I have to use the Gmail app or the Nokia mail app. I don't often delete my emails however so this doesn't bother me (You get 7GB+ of storage).
I have a HTC HD 7.
My emails sync as soon as they come in on the Gmail server.
I am not using an App. I am using Windows Phone 7.5 custom email solution.
Deletes fine on my SGS, but goes into trash or recycle bin. To permanently delete, need to go into these and delete. Not sure it's same as your problem.