I've used rackspace hosted email before, both the regular and the exchange versions. It works nicely and the users were very happy. It gets expensive though if you want push notifications on the blackberry, even without the exchange.

Google Apps has the advantage that it comes with docs and gmail - not just a standard email :O)

I've been on Fastmail for at least the last 7 years and find it to be an extremely reliable service. I've probably used them as the MX for over 20 domains.

I am migrating away from them however, because I've decided to consolidate all my hosting with a single provider (Linode). I can wholeheartedly recommend them though.

Are you going to be running your own mail then? (I don't recall linode offering mail hosting as a service..)