How to deal with exploding node_access queries?
I don't know how much of an answer this is, but: the approach I was taking to node_access that led to the original post was almost certainly wrong.  In particular, I was setting up separate gids for each item I was writing into node_access, rather than keeping gids associated with user IDs as they are almost surely meant to be.  After a bit of work, I was able to restructure this aspect of the site around this more correct approach, and was able to cut down the number of clauses added by node_access by about a factor of 10.  Life is a learning experience, I guess; I could probably elaborate a bit if anybody cares...