I work with Lotus Notes servers and there i use DNSBL, and private Black list domains plus symantec mail security for domino.
I am sure that these features are available to all the major mail servers.. try to put in some DNSBL servers addresses in your Exchange server’s configuration… you can define rules to reject mails from any domain ending up with .com.tw or whatever is bothering u (that is if you don’t have clients on that side of the world), Use some good antispam software on your Exchagne server to drop the spam.
I hope it will give you some guide line to fight against spam.
And remember Google is Man’s best friend after Dog. 🙂