So here goes ...
I think the bots work by searching for the file "wp-register.php" in domains, and using the known default behaviour of this file to register accounts automatically. So make the default behaviour not work ....
In wp-register.php, find:
$user_email = $_POST['user_email'];
$user_verify = $_POST[user_verify'];
as the next line.
$errors['user_login'] = __('<strong>ERROR</strong>: This username is invalid. Please enter a valid username.');
$user_login = '';
if ($user_verify == '')
$errors['user_verify'] = __('<strong>ERROR</strong>: You can only register if you are real!');
$user_verify = '';
<label for="user_email"><?php _e('E-mail:') ?></label> <input type="text" name="user_email" id="user_email" size="25" maxlength="100" value="<?php echo wp_specialchars($user_email); ?>" />
<label for="user_verify"><?php _e('Are you real?') ?></label> <input type="text" name="user_verify" id="user_verify" size="10" maxlength="15" value="" />
Unless the person registering puts anything non-blank in the "verify" window, the registration won't work, I think - and a spambot would not know to look for this yet. However, by putting particular words in for verification - change the question on each website, or whatever - this fix could be made non-generic.
I'll let you know if it cuts down the spam.
UPDATE: A more usable (as it is a plugin), but less effective (as it is reactive rather than proactive), method of achieving the same thing can be found here.
ANOTHER UPDATE: Here's another plugin that works by blacklisting.
YAA: Due to the way special characters are formatted, you're probably better off reading the code for this on the WordPress.org Suggestions site. Here is a link to the relevant page - the code is about half way down.