MessageLabs are OK as far as filtering and spam blocking goes, but there are way better (and cheaper) solutions out there. A problem I've found with MessageLabs in the past is that they're always changing the IP address ranges used by their servers. A few of our customers are always logging support calls because they aren't receiving email, only for me or one of the other guys to find that the ACL on their PIX/ASA/StoneGate FW doesn't contain the address range that MessageLabs claim to be relaying from.
Try MXSweep. They're very good and VERY cheap - highly recommended.
Google offer a similar service which is apparently based on Gmail, which is also meant to be very good.
But, if cost isn't an issue, a managed email service from Postini is about as good as it gets IMO.