I have found another interesting detail about this bug 1.3. It turns out that when creating a custom content object under a view-restricted page, and then unrestricting that page, the custom content can still not be found through CQL by users who previously didn’t have access to it. Saving a new version of the custom content fixes the problem.
This confirms my suspicion that the problem is that when changing the restrictions of a page, the restrictions of the custom content underneath it are not updated in the search index.