Adding per-blog users

I use a multisited WordPress to support a large number of sites. Each of the site owners needs to be able to set up protected pages with group-based access restrictions. The most sane way of doing this would seem to be to allow site owners to create and delete special restricted users (not a problem) and assign access rights to them (handled by a slightly customized User Access Manager plugin).

There is one problem, however: Users need to be unique within the entire network so if someone has already signed up for one site they can’t sign up for any other site in the network. (Well, technically they already are but they don’t know that.)

What I need is something that uses the regular WordPress login form, new user mail etc. but doesn’t pollute the network-wide user table. Essentially, a way of storing users in a per-site table and making them transparently accessible to certain core WordPress functions. I don’t mind of the per-site users are just the bare minimum neccessary to log in and read protected content.

What would be the least-invasive way of doing that? I’m not enthusiastic about becoming incompatible with vanilla WordPress and having to port my changes to every new version by hand.