I tried outlook.com IMAP with apple mail recently, and I must say my experience was not as good as newegemac's. It worked horribly for me. Very basic things did not work reliably, such as moving mail between folders. It would occasionally actually move it, other times it would spit out some random error about something not able to be read from [insert microsoft server here], other times it would just appear to do nothing at all. It seems like their IMAP support is still very much in its infancy, at least that was my experience. I also had a problem where new messages wouldn't appear in my inbox until I switched to another folder and then back to inbox. I had similar issues with all folders, if I moved something to another folder and then switched to that folder, it wouldn't appear until I fully synchronized the account and then switched back to the folder and other such gymnastics (if it even decided to move the message at all, as I mentioned above a lot of times it just wouldn't work). Downloading mail to my inbox and deleting mail to trash were the only things that worked, folders were giving me nothing but trouble for some reason. I don't know why I had so many issues with it when everyone else reports it works fine

I guess it just hates me lol.
I recently started trying out fastmail's 2 month trial, and its IMAP support is flawless and totally standard/vanilla. Everything works perfectly with apple mail for me with this service with absolutely no tweaking or workarounds required, even the archive button. I'm really happy with it so far, I've set it up in mail.app on my macbook, on my android phone's mail app and in em client on my windows machine, works great on all of them. It actually has a pretty nice, clean web interface too. downside is they don't offer any calendar service, and only has contacts sync via LDAP (which is read only).
edit: but apparently they are working on Carddav contacts support and Caldav calendar, so this could be an excellent all-around solution once they implement that!:
https://twitter.com/FastMailFM/status/393138107505070080
Anyway, I definitely agree with newagemac about cutting gmail either way. If you use 100% webmail gmail is excellent, but for anything else its disappointing and a PIA. I recommend anyone try outlook.com themselves first, since I seem to be the only one that had a lot of issues with it, but fastmail is another excellent alternative if you want quality IMAP access that works reliably with any standards compliant IMAP client (although it is a paid service, but 39 dollars a year for the enhanced plan isn't that bad and there's a free trial).