[taa]

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)