1) /tell filters. Add an option in character or system configuration that allows players to block tells from anyone not in their FC, friend list, linkshells, or any combination thereof.

2) Implement a system where players have to add each other before either person gets notified that someone tried to add them (because bots are sending friend invites).
Ie. instead of Tifa Lockheart getting a "Cloud Strife has sent you a friend request. Accept / Decline," popup, she would also have to send Cloud Strife a friend request to have him added.

3) Add a report spam option to the chat log's context menu.
Have the client automatically report the offending tell and add the sender to the blacklist.
Show a confirmation window giving the sender's name and the body of the message to prevent mis-reporting.

4) Add a "Purge Deleted Characters" option to the blacklist so we don't have to do it individually.

PS. I can't believe there's 1000 character limit on a forum. Really SE?