Deleting Messages in Google Mail when using an IMAP client
If you do not correctly delete a message from your inbox or one of your folders in your IMAP client (e.g. Thunderbird), it will still appear in the '[Gmail]/All Mail' folder.
The reason this occurs is because of Google Mail's use of 'Labels' instead of folders. Deleting mail in some clients 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 correctly delete a message from all folders it must first be moved to the '[Gmail]/Bin folder', this folder must then be emptied through the client. The latest versions of popular email clients handle this process with ease so you are strongly advised to upgrade.
For client-specific settings that affect deleting, storing messages and drafts please see the individual client settings at the link below.