Are you a service provider or a single company ?
Users as individuals, or users as a corporate email system ?
Who is having the problem :
Mostly a single user ?
multiple users, same domain ?
multiple users, multiple domains ?
Once you get on the list of spammers, there is no getting off, it will only increase. Even with the best filtering. Its like trying to catch water with a strainer, and a bunch of paper towels lining the strainer. Eventually you reach saturation and its starts flowing.
We have a few clients that complain about spam, but are constantly signing up for "free" things like daily inspirational quotes, publishers clearing house contests, and a bunch of other things. They cant seem to understand the relationship about signing up for stuff and then getting bombarded with junk.
I put together a plan for one of our clients (a school) to migrate everyone to new email addresses on the domain as many of the staff were getting bombarded with junk. Its a strict plan that i can share with you the procedure. Part of the plan includes user training, and a list of new policies and in addition an "acceptable use policy" explaining that the companies email is to be used for company/business purposes only, and not personal things. ( "airline miles", "daily coupons", etc) And if they do need to sign up for something a new temporary email address is created for it till it is determined to be legitimate.
Its a little extra work, but it makes a tremendous difference.
www.HawaiianHope.org - Providing technology services to non profit organizations, homeless shelters, clean and sober houses and prisoner reentry programs. To date we have given away over 1,000 free computers.