of the first two, it essentially comes down to whether the set of filtered results is expected to be much larger than the set of authorized results or vice versa

I was thinking this direction. However both may return large (>10^6) result sets - unknown in advance.

then yeah you'd want to paginate first and call

BulkCheckPermission

I can not paginate first because, the entire first "page" may vanish because entries may not be permitted or (the other way around) entries may not satisfy the criteria. I think, I could start with (let's say) 1000 on both sides hoping that the "intersect" would be large enough to "fill" the first page (e.g. 25). If not I would need to "expand" but this could result in many requests to fill the first page. No?

that's correct, yes