I have Customers using the following three third-party services. All of the Customers had the arrangements in place before I began contracting for them, so I don't have any experience initiating the service. All three Customers are happy with the service being offered (spam, virus filtering, blocking unknown recipients, optionally scanning outgoing mail and adding disclaimer lines).
MXLogic: Servicing a Customer with nearly 200 mailboxes on Exchange 2007 and providing secondary MX service, virus and spam filtering.
MessageLabs: Servicing a Fortune 1000 Customer with nearly 2,500 mailboxes on Exchange 2003 and providing secondary MX service, virus and spam filtering, and outgoing SMTP relaying.
Google Postini: Servicing a Customer with 250 mailboxes on Exchange 2007 and providing secondary MX service, virus and spam filtering, outgoing SMTP relaying, message archiving (inbound and outbound), and disclaimer stamping on outgoing email.
All three of the services above work by being your "primary MX" to the Internet, and then delivering to your SMTP server (which is, ideally, refusing incoming SMTP requests from all other servers besides the third-party filtering host).
The last time I looked only Google Postini, of those three, published their prices w/o requiring you to contact a salesperson. That was an immediate "sell" to me. We're going to be putting at least 2 more Customers up on Postini because of the low price and effectiveness of their service. For many small companies the cost of third-party filtering is a fraction of the cost to purchase hardware and an operating system (amortized over the warranty lifetime of the gear), maintain that operating system, and obtain a subscription for filtering software (or, in the case of open source filtering software, maintain a relationship with a service provider to provide upkeep for the filtering software). I really prefer having filtering on a server in-house, but the cost numbers don't always make sense.