Most of our users log in with external (Shibboleth) authentication. A lot of these queries show up in our MySQL slow query log.
We tracked down these queries to a set_field function call in the update_user_record function in moodlelib.php. The user table has a unique key on the (mnethostid, username) pair but not on the username field alone. It also makes sense that (mnethostid, username) is unique and username is not, because users across different MNet sites can happen to have the same username. The set_field function call should have specified the mnethostid together with the username but it does not. Our site does not use MNet but if it did, the function call could have incorrectly updated records of more than one actual user.
The same logic exists in the code we are using (1.9.8) as well as in MOODLE_19_WEEKLY and HEAD.
Also, the update_user_record function updates multiple fields of a user record by calling the set_field function multiple time. They can be replaced with a single update_record function call.