I just want to throw my hat in the ring here and endorse AppRiver. We use for about 10 clients. It's expensive, but they have pretty good extras on top of the Exchange service such as great customer support, easy migration to new versions of Exchange, spam filtering, and a powerful control panel which I can "guest administrate" to help my customers quickly and easily. They've never gone down for us either.