Since 1.7 the evaluation of role overrides was a great source of confusion. I never understood it properly until I actually had to do some changes in the code. Some two weeks ago I started a sample implementation of new enrolment framework. When I got to function get_users_by_capability() I realised there is no way to improve performance of it. Also after spending a few hours studying the accesslib.php code and reading docs at How_permissions are calculated came to conclusion that we over engineered this, in fact I never saw anything like this anywhere else which is definitely not good sign.
How to solve this? Easy – steal ideas from known file system access control implementations :-D Each evaluation of access permissions is done for each group separately, you have access if you are member of at least one group that has access in given directory. It did not take long and I replaced the current complex permission evaluation code with new much simpler version that matches known filesystem concepts – yay!