Update: Totally rewriting/simplifying this question now that I've zero'ed in on the core issue.
I'm sharing an Account, Program B with a public group called Access Program B's Data. As part of that account sharing record, I'm including Read/Write access to all cases linked to that account. (For the curious, this sharing record is set up in an account trigger which is working properly; the sharing record exists with all the correct settings):
However, not all of the related cases are being shared properly.
For most of our cases at this desk, the sharing works correctly. Members of Access Program B's Data have access to the case records as expected. For these cases, when you click "Sharing" on the Case record, there's an account sharing record as one would expect:
On other cases, the sharing is not working. Members of the public group do not have access, and no account sharing line shows up in the sharing list. Curiously, all of the cases which are not sharing properly are owned by queues (rather than by users) -- but there are other cases, also owned by queues, which are sharing properly.
UPDATE: This appears to be a platform bug. Changing the owner of the affected cases, and then changing it back forces a recalculation and resolves the issue. SFDC support is looking into the problem, and I'll let people here know if there's any useful information when it's resolved.