Your email is not being deleted because it is probably in the All Mail folder from Gmail. Here is what worked for me. I set up my Gmail accounts using Mac Mail. I have all my mailbox behaviors checked except for drafts. Everything is set to "Never". Make sure "Show in IMAP" for "All Mail" in Gmails web interface is checked. If you try to hide this folder, it could cause you problems such as your email disappearing from your local inbox.
Also turn off Mac Mail's junk mail filtering and let that be done through Gmail.
With this setup, if I delete an email from my inbox, it goes to the trash in my mac mail as well as to the trash in Gmail's web interface which will be deleted 30 days after it was put there. It does not get archived in All Mail which is probably happening to you. Sent messages are stored until I delete them as well.
Do not delete junk mail manually. Let Gmail delete it after 30 days so it will learn what is junk. If you get junk mail in your inbox, drag it the junk mail folder. That way you can teach Gmail what is also junk.
If you manually move a message out of your inbox and into a local folder on your mac for example, a copy of the email will reside in the "All Mail" folder. So in this instance, you will have to remove emails from the Archive folder (All Mail) on your mac to your local folders if you want them removed from the Gmail servers.
The only thing I have not been able to solve is if I manually delete a message that resides in my trash folder on mac, it will still be in the trash folder in Gmail's web interface waiting for the 30 day deletion period. In order for me to delete it permanently sooner, I have to manually delete it from Gmail's web interface. However, it will delete from all devices and the server if you delete the message from your trash folder on your iPhone or iPad if you are using the server's trash as your deleted mailbox.
Let me know if this helps, and if you have further questions.
