We had the same issue for our organization. We went with Postini services. Our mail servers are now configured to accept mail from ONLY Postini. This has effectively dropped our inbound mail to 10% of what it was before putting spam filtering in the cloud. In other words, all e-mail to my organization is 90% spam and 10% legitimate.
Be sure your edge mail servers are not configured as relay hosts for any domain but your private domain and that the relay point is from the inside out and no one can spoof your domain on the outside and relay messages.
One feature that Postini has that is useful is blocking directory harvest attacks. This has also significantly reduced inbound messages to legitimate addresses only.