Dave Rodriguez clued us into the query gymnastics to speed up permissions checks. However, it doesn't seem to work all the time. In some cases we've resorted to the distasteful method of selecting out all possible matches, with the permission value, and screening them out in Tcl.
I did have some success creating procs which return a "collection" of ids, which can then in turn be used like a table. This is very Oracle-specific, and is only practically useful in certain circumstances, particularly answering the question "who has privilege X on object Y?"
