I've been using google apps for hosting my personal email and I've been looking to move away from it. I would like some recommendations too.
I'd stick with Rackspace if it weren't for the fact that Exchange doesn't support the plus addressing.
Personally, I would need the ability to add email aliases. I use plus addressing rarely.