On the size of permissions table you're being somewhat pessimistic. The inheritance system and group-wide granting of permissions helps to cut the size down considerably.
SloanSpace V2 (dotLRN) has about 11,500 users, 16,000 mounted package instances (all those classes and forums inside classes etc), almost 550,000 objects and only 211,000 rows in the permissions table.
"only" 211,000 :) Hmmm... still much, much lower than your estimate, though.
In the rewrite I've done all queries are able to now take full advantage of indexes, so for SloanSpace V2 we're looking at 18 index probes to find a particular row - log2(211,000) rounds off to 18 I think if my mind's in order today. We've got a join against one other large table and a couple of small ones, it's not that bad.
