Having personally been utterly confused when initially investigating the various hosting options (shared hosting, web hosting, reseller web hosting, reseller VPS, VPS, VPS hosting, dedicated server - jeez no standardised terminology) and exactly what I should be checking for, I can now wholeheartedly recommend knownhost.com (VPS XLtx package) whom we've been using since Feb 2008.
We've currently got 10 top-level domains with up to 22 subdomains hanging off each one. Upwards of 70+ plugins (not all activated across all TLD's), with 130+ users.
Their uptime has been almost 100% and their turnaround of technical support requests is simply amazing (even on a Sunday night at 10pm!) No support request is too trivial for them and they've been more than happy to fix my bumbling amateur DNS mistakes etc. I can even describe what I need to do in non-tech speak and they understand what I'm saying - and often just do it for me!
Their knowledge and support of WPMU is pretty much non-existent, but that's fine as I've got you guys here!
And with the Dollar to UK Sterling exchange rate what it is at the moment, our bill every month is RIDICULOUSLY low. I can't believe I was even considering configuring our own server onsite. The support itself is worth the fee!
We also have a backup VPS with futurehosting.biz but I've yet to be as impressed with them...