You should have tried Brightmail on your in-house server ! I hope you weren't paying someone for anti-spam advice, especially given the type of things you've tried (challenge response = waste of time, incredibly frustrating for genuine senders ... everyone knows that) !
Messagelabs are OK, but quite expensive.
The Spamhaus Project is awsome if correctly implemented .... best of all, it's free for low volumes and dirt cheap for higher volumes (what message labs charges you for 10 users would probably get you a 500 user private feed from them).
(And no, I've no interest in Brightmail or Spamhaus ..... have just had a great deal of success with both products in various scenarios).
Of course, services such as MesssageLabs, Postini etc. do have other potential benefits which you may place more or less value on ....... but I'm not going to go into any more detail here..... there should always be some stuff left as an "exercise to the reader" when it comes to freebie forum tips.
