Mollom and Spamicide are not slowing down spam registrations
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.