Deleting IMAP messages
If you delete a message from your inbox or one of your custom folders in your IMAP client, it will still appear in [Gmail]/All Mail.
Here's why: in most folders, deleting a message simply removes that folder's label from the message, including the label identifying the message as being in your inbox. [Gmail]/All Mail shows all of your messages, whether or not they have labels attached to them. If you want to delete a message from all folders, move it to the [Gmail]/Trash folder.
If you delete a message from [Gmail]/Spam or [Gmail]/Trash, it will be deleted permanently.
For client-specific settings that affect deleting and storing messages and drafts, please see our Recommended IMAP client settings.
Important: Please note that if you're using an iPhone with software update 1.1.3 or later and you automatically configured IMAP by tapping the large Gmail icon in Mail, messages trashed from your iPhone will be moved to the [Gmail]/Trash folder rather than the [Gmail]/All Mail folder, where these messages are set to be permanently deleted after 30 days. For more information, please see our article on deleting and archiving on iPhones or visit Apple Support.
To avoid this type of deletion behavior, please manually configure your iPhone.