From a usability point of view, it'd actually be a great to maintain a list of plugins known to work or known to cause issues, i.e. whitelist/blacklist. Possibly, in the form of a simple Php array.
This would make it much easier to select plugins that work well.
Given that full and proper "network" support would be essential for _ANY_ plugin on a network install, it'd certainly be valuable information if people provided information on working plugins and those that seem to cause issues so far.
MU/Network compatibility should in fact be an attribute for all WP plugins, that is also checked prior installation.