We faced of one of the projects that we supported with large amount of spam registrations. But there were valid users with assigned roles that should not be deleted.

Short script was written to resolve this task:

<?php
require_once './includes/bootstrap.inc';
define('DRUPAL_ROOT', '<path_to_you_Drupal_folder>'); // optional
drupal_bootstrap(DRUPAL_BOOTSTRAP_FULL); // load Drupal to use Drupal API
$query = 'SELECT users.uid as uid FROM {users} LEFT JOIN {users_roles} ON users.uid = users_roles.uid WHERE users.uid != 0 AND users_roles.uid IS null ORDER BY users.uid DESC LIMIT 300';
$result = db_query($query);
while ($row = $result->fetchObject()) {
  user_delete($row->uid);
}
echo '300 spam users were deleted!'
?>

Let me explain this code in details:

If we would like to use Drupal API and DB connection in any separate script not in our custom Drupal module we need to start with these lines:

<?php
require_once './includes/bootstrap.inc';
define('DRUPAL_ROOT', '<path_to_you_Drupal_folder>'); // optional
drupal_bootstrap(DRUPAL_BOOTSTRAP_FULL); // load Drupal to use Drupal API
?>

Attention! You should put your path instead ''.
Some times script can work without 'DRUPAL_ROOT' definition, but some times can't like in our case.

Authenticated User role ID is 2. But there is no any record with that role ID in {users_roles} table, so we should select all user IDs that have no records in {users_roles} table users_roles.uid IS null.

And do not forget to exclude Anonymous user record users.uid != 0.
Other wise we can delete record with 0 UID from {users} table, that serve for Anonymous user purpose.

Start to delete most resent users ORDER BY users.uid DESC.

Due to user_delete() function require pretty large number of SQL requests it is reasonable to set some limit LIMIT 300.

If there are a lot of spam users you can set cron task, for example:

*/02 * * * *  /usr/bin/wget -O - -q -t 1 http://your_site.com/your_script_name.php >/dev/null 2>&1