Upgrade to latest MU version first. If you run into problems with that, report your feedback and the bugs you encounter to the MU Project.
Then Upgrade to WordPress 3.0. If you run into any problems with that step, report it to the WP Project.
As far as you're concerned for a quick test (not a mass test), you can do the test locally on a testserver (and invite some key beta-testers to test (remotely) on your machine). I would do that first anyway, because it will show if things heavily break or not.
Copy over your database and all files (that's "all blogs") to a testsystem. Re-map your domain in your hosts file to the testsystem, that will prevent you caring about domain name problems because of the migration to test. This info might be of help: Grep and Friends (collection of linux shell commands to install, backup and restore wordpress). (Feedback welcome)
So just copy over everything to the testsystem. Take something that is close to your server, e.g. probably something LAMP.
Then make a backup again (or a snapshot in case you're using a virtual system for that which is somehow recommended as those have snapshots actually build in which will make it easy to "replay" stuff and you don't need full performance).
Then do the upgrade. If you're already on the latest, you don't need to upgrade to the latest MU then, otherwise as already written I would do that. You can enable WP_DEBUG and watch warnings (I would code some logging here that will report problems with backlogs and name the plugins etc.) and all the like what's a sign of a problem here. I would fix as much that is easily fix or otherwise just kill plugins that are not expected to be updated any longer.
I have full understanding for the level of quality you want to offer to your users, just layout some key points for what you tell your users that a certain plugin or theme won't make it.
Or if you are a really nice admin, try to find out about those and perhaps you can crowd-source resources to get stuff updated. Sometimes a little higher donation (about 150+ USD or 100+ EUR) does wonders if you feel it's correct with the plugin or theme's author(s).