Hmmm, ideas yes.
Creating your own plugin to remove a meta_box and then add your own is easy enough.
Working just with the post_categories_meta_box from edit_form_advanced.php you can easily enough remove the original post_categories_meta_box with a plugin ... and
Create and Add your own custom_post_categories_meta_box with(or without) all the bells and whistles you like.
Create your own plugin replacement function for wp_category_checklist to filter the get_categories based on user role/cap, ID, multiple cat ids etc etc.
You can set up a plugin to work fine on a single blog with multiple users, but making sure categories and user roles are static across many blogs is another trick. For instance, in WPMU categories with same name have same ID from blog to blog, once the cats are added to the new blog. So '&hide_empty=0' will need to be added to the get_categories so cats list on a blog that has no posts in that category, yet. Anyway,
Other ideas: http://wordpress.org/search/wp_category_checklist?forums=1