Actually, I stuck debugging this more. It seems that the problem is probably connected to the visibility settings of the images. If you make a public post, and attach a private image, the image is not visible. The same happens if you share a post to "Friends", but the image has visibility to "Followers", even when Friends is a subset of followers. It seems that some users on our server have managed to attach a new image to a post (upload while writing the post), and still the image has different permissions than the post.

How I would have assumed it to work: When an image is added to a post, the image inherits the visibility permissions of the post.