I set up Mail.app to use Gmail’s IMAP feature when it was released a few months ago. One thing wasn’t clear at the time, and that was how Mail.app would handle Mailbox Behaviors with the IMAP settings. Unfortunately, I forgot about it, and only realized recently that emails deleted in Mail.app were being routed to Gmail’s Trash (and deleted after 30 days) rather than being sent to All Mail.
If you’re using these together, make sure that “Move deleted messages to the Trash mailbox” is unchecked under Preferences… Accounts… ((account name))… Mailbox Behaviors.
More info at the Gmail IMAP FAQ.