The challenge is that Gmail uses "Labels" to attach to messages, and messages can have zero or more than one label, while IMAP puts messages in folders (Inbox, Trash, etc) and every message is in one, and only one, folder. Thus, when Mail.app tells the Gmail server to delete a message from the Inbox, the Gmail server cannot reliably tell if it should just remove the "Inbox" label from that message (leaving it with one fewer label, possibly still having other labels, or maybe no label but still available in the "All Mail" view) or if it should more permanently remove the message completely from the database.
The "fix" is to setup Gmail to not show the messages in multiple IMAP folders (by turning off the "All Mail" folder) and to also have the Gmail servers "expunge" the message when the Mail.app tells it so rather than doing it "automatically", even though that (default) setting on the Gmail server seems to imply that the "auto" setting would be what was desired.
I have not tested ALL of these settings (I mostly rely on the "30 days in the trash" feature of Gmail to empty things: https://support.google.com/mail/answer/7401?hl=en ) and I have only recently updated to "El Capitan", but things do not seem any different from my Yosemite, Mavericks and earlier experiences. Note that as of May 2020 I am still using the same setup in systems up to and including Mojave, but have not done any testing of Catalina. The way the system works seems to be the same using either a "regular" @gmail.com account or a "Google Apps for Domains" @yourdomain.com account.
I do, however, have things set so that email does get put into the trash properly on the Gmail side of things, and it looks like there are settings available to delete things immediately, and it works on my system in the way I want it too.
So the detailed instructions are:
At http://gmail.com/, log in to your account and select the following:
"Settings" -> "Forwarding and IMAP"
Check "Enable IMAP"
For "When I mark a message in IMAP as deleted"
- Check "Auto-Expunge off - Wait for the client to update the server."
For "When a message is marked as deleted and expunged from the last visible IMAP folder"
- Check "Immediately delete the message forever"
(I have my system set up to "Move the message to the Trash" and rely on the 30 days mentioned above)
You need to select the "Save Changes" button at the bottom for this to take effect.
These settings will only invoke the deletion (or move to Gmail Trash) when the message no longer has any Gmail tags associated with it, or in other words, when an IMAP client removes the message from all of the IMAP folders. Since one of the "folders" that can be displayed in a Gmail IMAP client is "All Mail", just deleting a message from the Inbox of the IMAP client will not cause it to go bye-bye. Thus we need to limit the "Labels"/"Folders" that Gmail exposes as IMAP folders:
On Gmail, select the following:
"Settings" -> "Labels"
Check the "Show in IMAP" checkbox for "Inbox", "Sent Mail", and "Spam" and UNCHECK the "Show in IMAP" checkbox for all of the other "System Labels". Any user generated non-system label can be set to "Show in IMAP".
Note that unchecking the "All Mail" "Show in IMAP" checkbox might make a whole bunch of email that has no other labels (is in no other IMAP folder) no longer be visible in Mail.app or any other IMAP client. Using the Gmail web interface to search up these "orphaned" messages and adding the Inbox label or some other label that is shown in IMAP would make them visible again to Mail.app.
With the Gmail system set in this manner, I find that the best Mail.app settings to use are to have the "Mail" -> "Preferences" -> "Accounts" set up for the Gmail account in question set so that "Mailbox Behaviors" is set to only "Store on the Server" for the "Sent" and "Junk" mailboxes. I have those two boxes checked, and have the boxes for "Drafts" and "Trash" unchecked. These two need to be unchecked because we have set the Gmail server to not expose those boxes as IMAP folders.
I only rarely go to the Gmail web interface, doing almost all of my interactions with Gmail through Mail.app or the iOS Gmail app. Some of these settings might have alternative setups if one did a lot of website interactions.
For Mark's desired outcome of deleting the messages immediately, the above settings should work - when a message is moved or deleted from the Gmail Inbox and Spam folders, it should immediately be deleted from the Gmail server. The message could still be available in Apple's trash can, but that is not linked to the server's trash can. (If the "Move the message to the Trash" setting was set on the Gmail server, the server will move it to the server's trash, and thirty days later, it will be gone). I do not know if Mail.app will send the "expunge" signal to the Gmail servers immediately, or only after the local Mail.app trash has been emptied, or on some other synchronization schedule.
An alternative might be to have the Gmail server expose the server trash as an IMAP folder and have Mail.app store the trash on the server. With the "Immediately delete the message forever" server setting set, this should behave as desired - emptying the trash in Mail.app should cause the Gmail server to delete the message forever. I have not actually tested this immediate deletion setup, so if anyone has any actual experience with this, please let us know.
The key to all of these is to NOT expose the "All Mail" as an IMAP folder, and to counter-intuitively have "Auto-Expunge" turned off so that the options for deleting the mail are available to be selected.
This also will not have a direct impact on messages manipulated via the Gmail website - when you use the website to remove all labels from a message, that message will still be in the "All Mail" collection, and will not be immediately delete or moved to the trash. It might be necessary to go to the Gmail website and look through the "All Mail" collection and dispose of anything that has no labels.
Note that in Yosemite and later, when you set up an account that Mail.app recognizes as a Google or Gmail account (including accounts of organizations that are hosted at Google), it will not set up the account designated as "IMAP", but will instead designate it as "Google IMAP" and will select and then grey out the "Advanced" setting of "Automatically detect and maintain account settings" which can cause the SMTP account associated with the "Google IMAP" account to also have this Advanced setting of "Automatically detect and maintain account settings" to be selected and greyed out, so it cannot be unselected. This also seems to happen when system upgrades happen and mail accounts are updated when the Mail.app program is updated.
To force the creation of a "regular" IMAP account, one can create a new account in Mail.app but use bogus IMAP server information that Mail.app does not recognize as Google servers (such as "smtp.notgm.comm" and "imap.notgm.comm"). After the account is created as a "regular" IMAP account, my testing indicates that changing the server information to the correct Google server does not change it into a "Google IMAP" account, and the "Automatically detect and maintain account settings" can (and probably should, if you don't want things to get changed without your knowledge) be unchecked. I do not know if the "Google IMAP" account designation has any other features or abilities that the "regular" IMAP account does not.
For completeness, here are the required settings for Google's Gmail system as of Nov 2015:
Gmail IMAP user name: Your full Google account address (e.g. "firstname.lastname@example.org" or "email@example.com")
Gmail IMAP password: Your Google account password
Gmail IMAP port: 993
Gmail IMAP TLS/SSL required: yes
Gmail SMTP user name: Your full Google account address (e.g. "firstname.lastname@example.org" or "email@example.com")
Gmail SMTP password: Your Google account password
Gmail SMTP port (TLS): 587
Gmail SMTP TLS/SSL required: yes
Let me know if this works for you and we can update the answer with any detailed improvements you might discover.
More info is at https://web.archive.org/web/20151022160428/http://jeffschuette.com/2012/03/07/setting-up-apple-mail-to-rock-and-roll-with-gmail/ and https://web.archive.org/web/20151108133234/http://jeffschuette.com/2013/11/05/apple-mail-and-gmail-part-deux/ for Mavericks where Mail.app handles the "All Mail" label better than it previously did. For myself, I have kept the "All Mail" label not exposed to IMAP even in Mavericks and have continued with this practice in Yosemite and El Capitan.
This article from MacWorld back in 2013 covers some of the same info, and has some screenshots: