We use MessageLabs and had been very happy with them. However, they’ve been recently taken over by Verizon and the transition has not been smooth. I would have recommended MessageLabs without hesitation six months or a year ago, but since being taken over by Verizon, I’ve found it much harder to get service or even get someone on the phone who understands what I’m talking about. I’ve handled basic mail routing for years, and if I’m talking to a provider like this, I should not have to explain what I mean by a “handoff to the recipient domain.”
Unfortunately, I have no purchasing authority, so I have to make do. Good luck!