If the 3rd-party firm is sharing 1 Exchange server over several clients, they may not want to implement further spam-blocking techinques, or may at least lag in implementing. They may also ask for more money to license and install filtering software on the server.
You could research an external blocking service such as MXLogic/Postini/etc, where you’d direct your domain’s MX records to the service, and they would forward clean mail to your 3rd-party email server.
If using the Outlook client, why not try a free client-based filter such as SpamBayes? (http://spambayes.sourceforge.net) It blocks based on personal email habits, and many times works better than server/service-based solutions.