Do you have any anti-spam mods on your site? Anti-ACP and the StopForumSpam have been working wonders on my forum. Basically the ACP, if I remember right, simply stops people from trying to register with a username that's listed in the StopForumSpam database. It might put off potential legit members from joining, especially if the name they want to use is in the database, but it does help, and I just encourage all new registerees that if the name they want to use is in SFS, to use a different username that's not likely to be in the database.
It is not a good idea to check usernames against the stopforumspam database. It causes alot of false positives as alot of usernames are in the database including the name Ashley. Names like Matthew are also in the database.
It is best to check emails against the stopforumspam.com database and IP's also although checking IP's may cause a few false positives to although nowhere near as many as the usernames.