Demystifying Hybrid Free/Busy: Finding errors and troubleshooting

I hope this isn't a repeat fix (didn't see anyone comment yet), but I hope this saves someone from the immense amount of time we put into it. Below was our scenario (obviously you'll have to fix some names for your environment):

Issue: Free/Busy does not work from Cloud/EXO to On-Prem, but the other way works fine. If a cloud user has Reviewer or higher access to an On-Prem calendar, they can see the calendar entries but still not see Free/Busy in the Scheduling Assistant.

Symptoms:

The Remote Connectivity analyzer comes back clean on Autodiscover and EWS, as does most any other test in existence except for these:
• EXO PS: Test-OAuthConnectivity -Service EWS https://<OnPremFqdn>/ews/exchange.asmx -Mailbox "<CloudAccount>" -Verbose | FL
System.Net.WebException: The remote server returned an error: (500) Internal Server Error.
• EXO PS: Test-OrganizationRelationship -Identity "O365 to On-premises…" -UserIdentity <OnPrem-MailboxAddress> -Confirm
Step 5 failed - Id: AutodiscoverServiceCallFailed - Status: Error - Description: The Autodiscover call failed.
• Free/Busy Test: https://testconnectivity.microsoft.com/tests/FreeBusy/input - This error will lead you back to checking the linked Exchange Online-Application Account and its RBAC for permissions. In our case the account *WAS* properly linked and all the proper permissions *WERE* there. This is probably the biggest indicator for this issue, the complaint of permissions and confirming all permissions were/are there.
Free/Busy Lookup failed with exception: Proxy web request failed. , inner exception: System.Web.Services.Protocols.SoapException: The application is missing a linked account for RBAC roles, or the linked account has no RBAC role assignments, or the calling users account is logon disabled.

Cause:
GPO > Computer Configuration > Windows Settings > Security settings > Security Options > “Network access: Restrict clients allowed to make remote calls to SAM” on Domain Controllers, this reduces the SAM database network access and is needed for Cloud to On-Prem free busy, best practice hardening is to have this set to Administrators only.
Note: You can check to see if this exists and has info in the string, if it’s there you can use Resultant Set of Policy to figure out which policy implements it: HKEY_LOCAL_MACHINE\System\CurrentControlSet\Control\Lsa\RestrictRemoteSam

Resolution:
Add “Exchange Servers” the “Remote Access” Allow permission on the policy on Domain Controllers. Once the policy updates, gpupdate /force, it should work immediately.

The back-end team came back with this article. We used this workaround to confirm it was the cause and then narrowed it after to leave the security hardening in place:

https://docs.microsoft.com/en-us/troubleshoot/windows-server/group-policy/authz-fails-access-denied-error-application-access-check 

Note: As a warning, while clearing it did work around the issue immediately, putting it back did *NOT* immediately break it again (making it take more time for us to find the true fix). We had to reboot the DCs after re-applying it for it to break again, but then adding "Exchange Servers" to it worked right away.