If I had the know how and authority, what I would do is:

Set up a system that detects key words (and the clever ways spammers use to bypass such filters)

If enough reports are made, the system checks the reported messages for those key words and then surreptitiously flags a spammer's account so that any and all characters that currently exist or are made in the future are phased (in much the same way inn rooms and the squadron room are).

This special phase would have npcs made to look like players running around the towns and a few automated messages in public chat channels to give the illusion that nothing is wrong.

The spammers would still be able to log and spam their messages but only other spammers would see them. Let them advertise to each other and get them out of our space while still getting their sub money. :P