Hosted SPAM Solution

I am sure there are lots of comments on this. I currently have about 550 mailboxes and have used a Barracuda SPAM appliance for a couple of years but I have noticed thatin the past 6 months the amount of SPAM messages that have come into our network has more than doubled. I am needing some recomendations for a hosted solution such as Postini, which the parrent comapany uses. I can not help but think that if I reduce the amount of SPAM messages entering the network then I can free up some bandwidth to be used by legitimate traffic.