You've suggested Honeypots - good idea, probably doing it already?
OP is suggesting the honeypot idea (also used vs. malware, e-mail spam, etc.) and SE should certainly do it if they aren't already!
I am also leaning toward the whitelist or communications prefs approach:
Friends can: [√]tell [√]invite [√]invite to alliance [√] invite to FC ...
or
Allow /tell from: [√]friends [√]party [√]fc [√]linkshell ... [√]whitelist [ ]spammers [ ]anyone
...
The main disadvantage is it would probably kill off random global /tell, which is a nice feature if it's to/from real players and not RMT spambots.