Galileo has:
select count(*) from acs_permissions;
count
--------
383347
(1 row)
and getting this speed:
132 ms 0or1row dbqd.acs-tcl.tcl.acs-permissions-procs.permission::permission_p_not_cached.select_permission_p: 0or1row nsdb0
select 1 from dual
where exists
( select 1
from acs_object_party_privilege_map ppm
where ppm.object_id = '1228' and ppm.party_id = '16319' and ppm.privilege = 'dotlrn_browse' )
As you see, the permission call has been changed lately, with 500K entries on acs_permissions you should be fine I think (though it can still be improved), specially since your db server if bigger than ours.