I think one way would be to disable pasting text into chat (or disable it all together). But then they'll probably use macro or something, but I'm pretty sure it's illegal so you can ban them like you do now (haven't read ToS but that's the case for most MMOs). Of course it won't get rid of every bots but a majority of them. Anyway why would you need to paste something in the chat, I don't think that's used a lot so it won't be missed by a lot of players. Another way would be to enter a captcha when you login for the first time, it would definitely slow them but I know some players don't like this.
Unfortunately, there's no easy way to eradicate this threat that plagues every F2P MMOs. I do hope we get rid of them someday.