I'm not sure if this is specific in some way to our install, but I thought I'd share because it caused me so much pain before we fixed the problem.
We've been using the plugin "Email Users" on many of the sites in our fairly large network for a couple of years. It's always worked very well, even though it's officially not tested on a multisite install. It's been a great plugin, very useful for us.
Then sometime a couple of weeks ago, probably about the time we passed the 2000-user mark as the new semester began, we started having mysql failures several times a day. Intermittently, at odd times, mysql CPU usage would jump way up--as far as 205%, so it would stop responding until restarted from the command line.
I tried a lot of different troubleshooting steps, looked at the mysql slow queries log, and found that most of those times the cause was a query to the wp-usermeta table. But other times queries to that same table were going through quickly with no problem. But I could not figure out (my skills are not strong enough) anything beyond that.
Finally on Wednesday we had someone notice that every time she tried to email all students in her class using the Email Users plugin, that triggered the problem (we only noticed because she tried the email, mysql hung, I restarted mysql, she tried again, and it hung again.)
I deleted that plugin, nobody is using it anymore, and the problem is completely solved. No more issues and the site is fast and responsive and stable again.
Could it be that the plugin has some issue with very large (2k or so) numbers of users? I know it isn't promised to work with multisite anyway.