I've been yearning for native IMAP for a long time now. Essentially since the day I got my iPhone. It got much worse as Leopard approached and the great features in Mail 3.0 were making me drool. It wasn't a simple decision though. I moved to GMail for really good reasons and I refuse to go back to running my own mail server. The result was to look at paid IMAP solutions but none of them offered the complete bevy of features I wanted. I finally identified both Fastmail and Tuffmail as having great services.
I was days away from switching to Tuffmail when GMail announced IMAP support. I eagerly awaited my account to be activated and started using it immediately. However, it's a mixed bag unfortunately.
GMail has some concepts that make IMAP hard. Like labels versus folders. Like not really liking to delete email. Starred emails. They've accommodated that in the IMAP solution, but also complicated things in a bad way.
For example, GMail IMAP has to expose a folder called "All Mail" that is the catch all for email that doesn't have any label. The unfortunate part of this is that mail clients will see two copies of everything, the one in a "folder" and the other one if the fake "All Mail" folder. This wreaks havoc with things like Smart Folders in Mail.
GMail also has some gnarly non-standard behavior. For example, when you send an email via it's SMTP service it automatically puts a copy in your Sent Items "label". This isn't normal, and requires that you configure your Mail client in somewhat non-standard way.
On top of this, the service is a bit slow and has had some hiccups for me. I may still end up signing up for Tuffmail but I'll give GMail IMAP a try since the price is right and the webmail client is so nice.