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:; and this:; and is ultimately ignored at but no solution was put in place for Drupal 6.
That means I’ll need to hack core to get this in.