This plugin will clean up the mess when your user database is full av invalid usernames.
Yes. It works great on MU!
Report any issues at the Google Code issue tracker: https://code.google.com/p/wp-valid-username-normalizer/issues/list
Read more about GPLv3 here: http://www.gnu.org/licenses/gpl-3.0.html
If we meet some day, and you think this stuff is worth it, you may buy me a beer in return. (GPLv3 still applies.)