Download and Access Issues for External Users with SharePoint “Anyone” link sharing option.

I am experiencing similar issues. It appears you have investigated the issue from various angles.
What makes it difficult to run a proper diagnostic is that there are so many variables to provide access (permissions) to a document (file) on Sharepoint. No logs are available to run checks as to what permission changes have been made in the past on a single document. I've had it happen that I was blocked from documents at a site that i am owner of. It wasn't clear what caused this issue, I am assuming a policy change from Microsoft. I was able to restore it, but it remains unclear why it occurred in the first place.