[Windows Phone 7 General] N8ter:
It has nothing to do with how WP7's client works. It works like any other IMAP client. Yahoo! tried the "WP7 Client" excuse and lost that battle. It's 100% due to Google's folder implementation. Most IMAP clients have to be coded specifically to work with Google's servers, because they use basically a proprietary label/folder structure due to their Label system (which is designed first and foremost for browser use, not client use).

GMail is a nightmare to work with in an IMAP client (many people agree, those who are used to it won't really care to agree or disagree).

That's cause All Mail is your real inbox, and Google does nothing but adds flags to mails. These flags correspond to labels and the only thing you see in the other folder are really copies of the other mail. When working with GMail through a web client it doesn't copy anything, it just sort of links everything, so if you delete a mail it simply removes the labels and moves the real item from All Mail to Trash.

Since standard IMAP clients do not support labels, they have to create a folder for each label and download a copy of that message in each of those folders. Furthermore, since they don't support the labels (again), when you delete an email from Work the IMAP client is dumb and has no clue that Work is only a Label and that same mail is also flagged for "Marketing" and "Travel", as well as "All Mail."

So, you end up with the Work copy going to your IMAP client Trash (not the Gmail Trash), and a copy still sitting in "All Mail", "Marketing", and "Travel."

When you perform a sync/reconcile the GMail servers may see the "Work" email is gone, but it doesn't mean delete this mail to the Gmail Servers. It means "Remove this Label from this email." And going by that statement, I can confirm that your information is wrong about knowing which mail was deleted. For people with Filters on their Gmail Account and nested Labels (Social Networks/Facebook etc.) it will only remove the Label that corresponds to the folder you deleted the email from in MOST IMAP clients (some code to work with Google's service in a specific manner). Most IMAP clients (even Microsoft Outlook, and IIRC Mozilla Thunderbird as well) had to push out major updates to their apps to cope with GMail's IMAP implementation (or rather, the Folder to IMAP coupling of GMail).

They have to map the IMAP Trash Folder to Gmail's Trash folder and make sure the emails are properly linked so that when one is deleted, everything goes to trash which stops the user's All Mail folder from growing to a ridiculous size (and is terrible for Junk Mail that gets through the Junk Filter and may be labeled). Should not have to jump into two clients just to delete an email :P

That is why you have to do twice the work.

Gmail is terrible for IMAP because it forces most IMAP clients (unless specifically coded to handle Google's service) to download a ton of redundant data and the folder structures are terrible.

It has nothing to do with WP7's client...

POP3 with GMail in Outlook, etc. with a fast (i.e. 5-10min) Poll Time is great (their servers are stable and fast). IMAP? Terrible...

Use AIM with IMAP and that's the way most services work. When you delete the mail, it actually deletes, and the folder structures are uniform and pretty much standard.

Google does this because they datamine emails (they don't personally read them, but they data mine them for targetted advertising, etc.). It's also why they had to make a specific GMail app for Android, even though Google Mail supports POP3, IMAP4, and ActiveSync (with HTML Mail support).

So, to end this long boring post... That's why I find it better to use POP3 or ActiveSync for GMail. IMAP with Gmail forces your phone to download a lot of redundant data which ups the battery life implications of GMail IMAP compared to i.e. AOL/AIM Mail IMAP (Yahoo! is terrible, and I haven't used it in ages so I cannot attest to how well theirs is implimented even without the data leak issue).