Yesterday I determined a compromise.  I’m going to keep using iCloud for contacts and calendars.  Google sync makes a mess of contacts, iCloud “just works.”  I’ll keep using Gmail for my main email.  I’ll access it through Apple Mail on the desktop and the iPhone’s built in mail app.

Here’s how I set it up to avoid duplicate messages and other craziness.  Log into Gmail’s settings and navigate to the labels tab.  Here you can control which labels show up in IMAP.  What I did was hide all mail, starred, and important from IMAP.  

If I’m going to archive a message I throw it into a folder in Mail.  I also created an archive folder for any mail I want to keep that doesn’t fit into a specific folder.  In Lion, Mail now has an archive and delete button.  Hitting the archive button moves the message to this archive folder, while hitting delete actually deletes the message.  If you need to access Gmail through the web app you still have all of your mail available to search in all mail and the new archive label.  I like this setup better because I have complete control over whether a message is deleted or archived via Mail’s native interface.

Problem solved (minus push on iPhone).