OK well if you have SBS2003 then your outlook clients connect to Exchange. In exchange you have public folders. Create a new public folder of type contacts and away you go :D Shared contacts.
Also depending on how many users you are, have a look at www.mxcontact.com