I've been going round and round trying to deal with a Gmail configuration issue. It appears that the issue I'm facing has something to do with the fact that Gmail doesn't really implement folders in a similar way to all other IMAP messaging services. Rather than creating folders, Gmail appears to keep a database and just adds tags indicating in what "folders" messages should appear when the user displays his/her Email. This approach, while very flexible, creates compatibility issues with Email agents on desktop, laptop and smartphone systems.
When messages are deleted, they really aren't deleted. They remain in the database tagged with "All Messages" and "Trash." When one deletes the message from the trash folder, the message isn't really deleted, the "Trash" tag is removed from the record describing the message. If one deletes the message from the "All Messages" folder, the record is marked with "Trash" and the mark for "All Messages is removed.
So far, about the only way I've found to really and truly delete a message, that is make it go away forever, is to chase it around the folders. I read the message in the inbox and press the delete button. The message is marked as trash but remains in the "All Messages" folder. I then select the "All Messages" folder and delete the message again. Then I go to the Trash folder and delete it again. Whew. Now the message is really gone
I've seen this behavior using Outlook, Mac Mail, iPhone Mail, K-9 mail and even the mail agent you provide with Android. Google, what possible benefit do you think this strange behavior adds to the experience one has using your product? I find it irritating.