So, Drupal makes extensive use of the LOWER() function in MySQL. The problem is that LOWER() ignores any indexes on columns and iterates through each row looking for a match. This is a problem if your user table has >600K rows. The problem was under discussion several years ago (see: http://drupal.org/node/181625; and this: http://drupal.org/node/83738; and is ultimately ignored at http://drupal.org/node/279851) but no solution was put in place for Drupal 6.
That means I’ll need to hack core to get this in.