Jon, if you don't have Account Activation set to by user, try that. If you have it set to that, you can try by Admin. You can also try username limits and passwords complexity, if you haven't already. Under Security Setting, have you seen this:
"Check IP against DNS Blackhole List:
If enabled the user’s IP address is checked against the following DNSBL services on registration and posting: spamcop.net, dsbl.org and
http://www.spamhaus.org. This lookup may take a while, depending on the server’s configuration. If slowdowns are experienced or too many false positives reported it is recommended to disable this check"
My last suggestion is uping the minimum times for registration and accepting terms.