Intermittent Access Denied errors for anonymous users
Figured this one out, not particularly efficiently (never really found a good way to backtrace this), but got there nonetheless.

The issue was coming from the Custom Permissions module, which I'd incorrectly written off as innocent early on in troubleshooting since I use it on other sites without issue. Whoops.

That module lets you create permissions via a UI for any path you'd like. We had one in place that created a permission that was already defined by core (managing blocks -- accessing admin/structure/block). Removing this redundant permission fixed our problem here. (Uninstalling the module also fixed the issue.)

I'll post an issue in that module's queue if it's reproducible with a clean install.