Mollom and Spamicide are not slowing down spam registrations I have a drupal 6 site. I'm using both Mollom and Spamicide.

Mollom is doing a great job at stopping spam comments but spambots are registering at an extremely high rate over 6 per minute.

Registration uses a captcha from Mollom and Spamicide but they seem to be going right through both. Spamicide slowed them down for about half a day but now that seems to be doing nothing.

Additionally, about 80% of the spambot accounts are validating their accounts through email - they create tons hotmail accounts with generic names.

Any ideas or recommendations on stemming the tide?

I've been trying to find a way of automatically blocking IPs that are throwing a high number of registrations or other suspect activity.
You can still try to use CloudFlare service, coupling with Mollom it's very effective.

Also, I'm not sure that they (bots I mean) are creating account e-mail to validate their account. The problem with Drupal 6, its has an algorithm to create the validation link that it's easier to reproduce (much harder with Drupal 7 as its has a secret key when you install).

Well, if with CloudFlare it doesn't slow down your spam problem, you can either change the validation algorithm or upgrade to Drupal 7.