Is your server in offline mode? If so, switching to online mode will certainly help..
I'd suggest using MCBans (if your in online mode). That's what I always did back when I managed my own server. Essentially if an account has been banned enough times (which is probably the case for spam/hacked accounts) then they won't be allowed on your server. Check it out, always loved that plugin!