Blocking Spam

At present my office is going through a network overhaul. Currently we are running Office 2003 but the inbox on most machines are being inundated with spam.

What’s the best / most cost effective way to tackle this issue?

Should we introduce 3rd party spam filters on both client and server sides?

Can anyone recommend any cheap solutions?